Graph Theory, Networks and Voronoi Diagrams

Updated 7 October 2026

In graph theory a graph is not a chart. It is a set of points, called vertices, and a set of connections between them, called edges. A road map is a graph once you keep only which places are joined.

The subject began in 1736, when Euler showed that no walk could cross each of the seven bridges of Königsberg exactly once. His argument used only the connections, never the shape of the town.

What are the parts of a graph?

A graph is built from vertices, drawn as dots, and edges, drawn as lines joining pairs of vertices. Each vertex has a degree: the number of edge ends that meet it. The handshake lemma links the two: the degrees always add to twice the number of edges. A square with one diagonal has 5 edges, and its vertices have degrees 3, 2, 3 and 2, so 3 + 2 + 3 + 2 = 10 = 2 × 5. The lemma holds because every edge has two ends, and each end adds 1 to one degree. A loop, an edge from a vertex back to itself, adds 2 to that vertex's degree. One consequence: the number of odd-degree vertices is always even, because the total is even. So a group in which exactly three people each shake an odd number of hands is impossible. Check a drawing by counting its edges twice, once directly and once as half the degree total.

See Vertices, Edges and Degree.

A simple graph has no loop and at most one edge between any pair of vertices. A complete graph joins every pair, so on n vertices it has $\frac{n\left(n-1\right)}{2}$n(n − 1)/2 edges. A bipartite graph splits the vertices into two sets, and every edge runs from one set to the other. See Simple, Complete and Bipartite Graphs.

A graph is connected when a route joins every pair of vertices. A tree is a connected graph with no cycle, and a tree on n vertices has exactly n − 1 edges: each new vertex needs one edge to join the tree, and a second edge would close a cycle. See Subgraphs, Connectedness and Trees.

A directed graph gives every edge an arrow. Arrows arriving give the in-degree and arrows leaving give the out-degree, and the graph is strongly connected when the arrows lead from any vertex to any other. See Directed Graphs and Strong Connectedness.

How do you store a network as numbers?

A network is stored as an adjacency matrix: a square table with one row and one column for each vertex. Write 1 in row A, column B when an edge joins A and B, and 0 when none does. For a triangle ABC with a vertex D joined only to C, the rows read A: 0 1 1 0, B: 1 0 1 0, C: 1 1 0 1 and D: 0 0 1 0. See The Adjacency Matrix. It is symmetric across the main diagonal, since every edge joins its two vertices both ways, and each row total is a degree: row C gives 1 + 1 + 0 + 1 = 3. In a directed graph, row A, column B records only arrows from A to B, so symmetry is lost. Check the table by adding the row totals: 2 + 2 + 3 + 1 = 8, twice the 4 edges.

Multiply the matrix by itself. Row i, column j of $A^2$A² counts the walks of length 2 from i to j, because the product adds up, over every middle vertex k, the ways of going from i to k and then to j. In the same way $A^n$Aⁿ counts the walks of length n. See Counting Walks with Matrix Powers.

A weighted graph carries a number on each edge: a distance, a cost or a time. The table holds that weight in place of the 1. See The Weighted Adjacency Table.

What do the route words actually mean?

Each route word says what a route may repeat. A walk is any sequence of edges, each starting where the last ended, and it may repeat anything. A trail repeats no edge. A path repeats no vertex, and so no edge either. Circuits are trails that end where they began, and a cycle is a circuit that repeats no vertex except the start. See Walks, Trails, Paths, Circuits and Cycles. On a square ABCD with the diagonal AC, the route A-B-C-A-D is a trail but not a path, because it returns to A. The words matter because route questions depend on what may be reused: covering every street is about edges, and visiting every town is about vertices. Two triangles sharing a vertex A show the gap between a circuit and a cycle: A-B-C-A-D-E-A uses every edge once but passes through A midway, so it is not a cycle. Its length, the number of edges, is 3 + 3 = 6.

An Eulerian circuit is a closed trail that uses every edge exactly once. A connected graph has one exactly when every vertex has even degree. With exactly two odd vertices the graph has an Eulerian trail instead, from one odd vertex to the other.

The reason is a count. Each time a trail passes through a vertex it uses one edge to arrive and one to leave, so every vertex except the start and the finish needs an even degree, and those two each have one unpaired edge. Any other number of odd vertices allows neither, and Königsberg had four. See Eulerian Trails and Circuits.

A Hamiltonian cycle visits every vertex exactly once and returns to the start. There is no degree test for it, so routes have to be tried one by one. See Hamiltonian Paths and Cycles.

What is the cheapest way to connect everything?

The cheapest way to connect every vertex is a minimum spanning tree: edges that join all the vertices, contain no cycle, and have the least total weight. Kruskal's algorithm finds one by taking edges cheapest first and skipping any that would close a cycle. Take four towns with roads AB = 2, BC = 3, AC = 4, CD = 5 and BD = 6. Kruskal takes AB and BC, rejects AC because A, B and C are already joined, then takes CD, for a total of 2 + 3 + 5 = 10. A tree on 4 vertices needs 4 − 1 = 3 edges, so it stops there. The greedy choice is safe because the cheapest edge across any split of the vertices into two groups belongs to some minimum tree. Equal weights may be taken in either order, which can give different trees with the same total. To confirm, swapping CD for BD costs 2 + 3 + 6 = 11.

See Kruskal's Algorithm for a Spanning Tree.

Prim's algorithm grows one tree from a starting vertex: at each step take the cheapest edge that leaves the tree and reaches a new vertex. The matrix method runs it on the weighted table. Cross out the column of each vertex in the tree, find the smallest entry left in the rows of those vertices, circle it, and that vertex joins. See Prim's Algorithm and the Matrix Method.

Routes that must cover everything

The Chinese postman problem asks for the shortest closed route that uses every edge at least once. If every vertex has even degree, an Eulerian circuit does it. Otherwise pair up the odd vertices, find the shortest route between each pair, and walk those edges twice. With four odd vertices there are three ways to pair them, so cost all three and take the cheapest. See The Chinese Postman Problem.

The traveling salesman problem asks for the cheapest cycle that visits every vertex once. No efficient exact method is known, so the answer is trapped between an upper bound and a lower bound. See The Traveling Salesman Problem.

The nearest-neighbor algorithm builds a tour: start at a vertex, always move to the nearest vertex not yet visited, and return home at the end. The best tour cannot cost more than a tour already in hand, so this cost is an upper bound. See The Nearest-Neighbor Upper Bound.

For a lower bound, delete one vertex and every edge that touches it, find a minimum spanning tree of what is left, and add back the two cheapest deleted edges. Every tour uses two edges at the deleted vertex and at least a spanning tree of the rest, so no tour can cost less. See The Deleted-Vertex Lower Bound.

How does a Voronoi diagram answer "what is nearest"?

A Voronoi diagram divides the plane into cells, one per site, and every point in a cell is nearer to that site than to any other. The nearest site to any point is then read from its cell, with no distances to compare. The border between sites A and B lies on the perpendicular bisector of AB, because that line holds exactly the points equally far from both. For A at (0, 0) and B at (6, 0), the bisector is the vertical line x = 3. A point at (2, 5) is on A's side: its squared distances are $2^2+5^2=29$2² + 5² = 29 to A and $4^2+5^2=41$4² + 5² = 41 to B. With three or more sites, each cell is cut down by the bisectors with its neighbors, and cell edges meet at vertices equally far from three sites. Test a point on the border: (3, 4) is 5 from both sites, since $3^2+4^2=25=5^2$3² + 4² = 25 = 5².

With more sites, draw the bisector of every pair and keep, for each site, the piece of the plane where it is nearest. See Voronoi Diagrams.

To find the equation of the edge between A at (1, 2) and B at (5, 4), first find the midpoint of AB, which is (3, 3). The gradient of AB is $\left(4-2\right)÷\left(5-1\right)=\frac{1}{2}$(4 − 2) ÷ (5 − 1) = 1/2, so the perpendicular gradient is the negative reciprocal, −2. The edge is the line through (3, 3) with gradient −2: y − 3 = −2(x − 3), which rearranges to y = −2x + 9. See The Equation of a Voronoi Edge.

Adding a new site cuts a new cell out of its neighbors, so the cells around it can only shrink. See Finding the Nearest Site.

The toxic waste dump problem asks for the point farthest from every site. Inside a cell you can always step farther from the nearest site, so the answer is at a Voronoi vertex, where three sites are equally near, or on the border of the region. Test every vertex, every corner and every point where a cell edge meets the border, and keep the largest circle that contains no site: its center is the answer. See The Toxic Waste Dump Problem.

A Voronoi cell is a polygon, so its area comes from its corners by ordinary mensuration. See The Area of a Voronoi Cell.

The mistakes worth naming

• Mixing up Eulerian and Hamiltonian. Eulerian is about edges and Hamiltonian is about vertices.
• Counting a loop once. A loop adds 2 to the degree, one for each end.
• Taking one edge too many in Kruskal's algorithm. A spanning tree on n vertices has n − 1 edges.
• Treating the nearest-neighbor tour as the best tour. It is an upper bound, and often not a close one.
• Drawing Voronoi edges by eye. Each edge is a perpendicular bisector, so find the midpoint and the perpendicular gradient.
• Trusting the drawing. Two drawings of the same graph can look nothing alike. Only the connections count.

Where this leads next

Matrix powers count walks here in the same way they track probabilities in the matrices and Markov chains guide. A Voronoi edge is found with the midpoint and gradient methods of the coordinate geometry guide. The degree count and the Königsberg argument are counting proofs of the kind set out in the logic and proof guide.