Registry
The great unsolved conjectures of graph theory, chosen where the obstruction is unusually well characterised, plus one solved control and one under dispute. Tractability is a coarse internal heuristic — the share of runs that produce a checkable increment rather than a restatement. It is not a probability of solution.
A graph on at least three vertices is determined, up to isomorphism, by the multiset of its vertex-deleted subgraphs. You can rebuild the whole from the deck of its one-vertex-smaller pieces.
Every graph that needs t colours contains the complete graph on t vertices as a minor. It is a sweeping generalisation of the Four Colour Theorem.
Every tree can be labelled so gracefully that the differences across its edges hit every value from 1 to the number of edges exactly once.
Every bridgeless graph has a collection of cycles that together cover each edge exactly twice.
You can colour a graph’s vertices and edges together, so that no two touching objects share a colour, using at most two colours more than the maximum degree.
Every bridgeless cubic graph has six perfect matchings arranged so that every edge lies in exactly two of them.
Every oriented graph has a vertex with at least as many friends-of-friends as friends — a vertex whose second out-neighbourhood is no smaller than its first.
Every graph in which every vertex has at least three neighbours contains a cycle whose length is a power of two.
The complete graph on 2n+1 vertices can be cut into 2n+1 identical copies of any given tree with n edges.