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$):
The union of all sets $X_i$ equals $V$. That is, each graph vertex is contained in at least one tree node.
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$.
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$.