Linked from

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

• Bipartite graphCompared with: Complete graphs with at least three vertices contain triangles and are not bipartite.

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

• Tree (graph theory)Compared with: Complete graphs with at least three vertices contain cycles and many alternate paths.

• Simple graphBroader topic: It is the maximally connected simple graph on a fixed number of vertices.

• Line graphBroader topic: The line graph of a complete graph displays dense edge-incidence structure.

• Connected graphBroader topic: Every complete graph is connected, with each pair linked directly.

• TreewidthBroader topic: A complete graph on n vertices has treewidth n minus one.

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

• Path graphCompared with: A path has only consecutive-vertex edges, rather than all possible edges.

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

• Undirected graphBroader topic: It is the densest simple undirected graph on a fixed number of vertices.

• Petersen graphCompared with: Unlike the sparse Petersen graph, a complete graph maximizes adjacency among its vertices.

• Vertex-transitive graphBroader topic: Every permutation of its vertices is an automorphism.

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

• Chromatic polynomialBroader topic: Its polynomial is the falling factorial, a direct formula illustrating the count.

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

• Regular graphBroader topic: Every complete graph is regular, with degree one less than its number of vertices.

• Vizing's theoremBroader topic: Complete graphs provide familiar examples whose edge chromatic number can be computed exactly.

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

• Wagner's theoremNarrower topic: K₅, one of the theorem’s two obstructions, is a complete graph.

• 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.

• Metcalfe's lawBroader topic: A fully connected network with n users has n(n−1)/2 possible pairwise links.

• 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.

• Bunkbed conjectureBroader topic: Its dense symmetry makes it a natural base graph for explicit probability calculations.

• 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.

• Lovász conjectureBroader topic: Every complete graph with at least two vertices has a Hamiltonian path.