I want to add the notion of **[Tree-Width](https://en.wikipedia.org/wiki/Treewidth)** to the list.

Roughly speaking, tree-width is a measure of how less tree-like a graph is. A tree has tree-width 1 while a $k$-clique has tree-width $k$. Tree-width has been used as a parameter for the analysis of a number of graph algorithms.

I think like every other clever definition, the definition of tree-width is something that makes a lot of connections clearer once we internalize it and yet, the definition is not something that is easy to come up with.

For reference,

> A tree decomposition of a graph $G = (V, E)$ is a tree, $T$, with nodes
> $X_1$, ..., $X_n$, where each $X_i$ is a subset of $V$, satisfying the following
> properties (the term node is used to refer to a vertex of $T$ to avoid
> confusion with vertices of $G$): 
> 
> 1. The union of all sets $X_i$ equals $V$. That is, each graph vertex is contained in at least one tree node.
> 
> 2. If $X_i$ and $X_j$ both contain a vertex $v$, then all nodes $X_k$ of $T$ in the (unique) path between $X_i$ and $X_j$ contain $v$ as well. Equivalently, the
> tree nodes containing vertex $v$ form a connected subtree of $T$.
> 3. For every edge $(v, w)$ in the graph, there is a subset $X_i$ that contains both $v$ and $w$. That is, vertices are adjacent in the graph
> only when the corresponding subtrees have a node in common.
> 
> The width of a tree decomposition is the size of its largest set $X_i$
> minus one. The treewidth $\mathrm{tw}(G)$ of a graph $G$ is the minimum width among
> all possible tree decompositions of $G$.