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
> X1, ..., Xn, where each Xi 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 Xi equals V. That is, each graph vertex is contained in at least one tree node.
> 
> 2. If Xi and Xj both contain a vertex v, then all nodes Xk of T in the (unique) path between Xi and Xj 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 Xi 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 Xi
> minus one. The treewidth tw(G) of a graph G is the minimum width among
> all possible tree decompositions of G.