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