graph theory: Quick Facts

Written and fact-checked by

The Information Architects of Encyclopaedia Britannica

Photos

A diagram of the historic Seven Bridges of Konigsberg, showing seven numbered bridges crossing over a river with multiple land masses, representing the classic mathematical problem.

Five diagrams illustrate types of graphs in mathematics: a simple graph, a multigraph with parallel edges, a complete graph with all possible connections, a graph with a loop, and a directed graph with arrows showing direction.

A geometric diagram illustrating an Eulerian circuit, with arrows tracing a continuous path along intersecting straight lines that form a closed shape connecting five points.

Hamiltonian circuit

A diagram of the complete graph K5, showing five points with every pair connected by straight lines, forming a dense network where several edges cross each other, illustrating its non-planar nature.

Two geometric diagrams compare the complete graphs K4 and K5, showing that K4 can be drawn without edges crossing (planar), while K5 cannot be drawn this way (nonplanar).

A geometric diagram of the complete bipartite graph K3,2, showing five vertices with three on one side and two on the other, all connected by curved lines representing edges between each pair of opposite sets.

Illustration of the gas, water, and electricity problem showing three utility buildings labeled W, G, and E, and three houses labeled A, B, and C. Colored lines connect each utility to each house, forming a complete bipartite graph K3,3, with a key identifying water pipes, gas lines, and electrical wires. The diagram demonstrates the non-planar nature of K3,3 in graph theory, as the connections cross over each other.

See All Images →

Topics

Hamilton circuit traveling salesman problem network theory linear graph graph combinatorics permutations and combinations

Dig Deeper: More Articles That Discuss This Topic

combinatorics: Graph theory

Key People

Paul Erdős

Paul Erdős

Hungarian mathematician

Endre Szemerédi

Endre Szemerédi

Hungarian American mathematician

Adleman, Leonard M.

Leonard M. Adleman

American computer scientist

Avraham Trahtman.

Avraham Trahtman

Israeli mathematician

Equations written on blackboard

Numbers and Mathematics