Linked from

The 31 pages that link to Complete graph, each with the reason it gives.

• Ramsey theoryRelated: Classical Ramsey numbers concern monochromatic complete subgraphs within larger complete graphs.

• Graph minorRelated: Complete graphs often serve as canonical excluded minors.

• DiagonalRelated: Its edges represent all possible vertex pairs, including polygon sides and diagonals.

• Brooks' theoremRelated: Complete graphs are one of the two exceptions to the degree bound.

• Graph homomorphismRelated: Maps to complete graphs encode proper colorings of the source.

• Turán's theoremRelated: The forbidden complete subgraph is a clique of the specified size.

• Cayley's formulaRelated: A labeled tree on n vertices is a spanning tree of the complete graph on those labels.

• Hamiltonian path problemRelated: Every complete graph with at least one vertex has a Hamiltonian path.

• Five color theoremRelated: The planar complete graph on four vertices shows that some planar graphs need four colors.

• Heawood conjectureRelated: Complete graphs provide sharp examples attaining the surface coloring bound.

• Burr–Erdős conjectureRelated: Graph Ramsey numbers ask how large a complete host graph must be.

• Erdős–Gyárfás conjectureRelated: Its abundant cycles make the required power-of-two length easy to find.

• Friends and strangers theoremRelated: Representing people as vertices makes every pair’s relationship an edge.

• Hedetniemi's conjectureRelated: Coloring a graph with k colors is equivalent to mapping it homomorphically to the complete graph on k vertices.