I want to add the notion of Tree-Width 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.

I want to add the notion of Tree-Width 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$.