Graphs

Whether a walk through a city can cross each of its bridges exactly once depends only on which pieces of land each bridge joins, and the problem is to find a language in which questions like that can be stated precisely and then settled by proof.

The previous lesson ended with the integers as one kind of discrete structure. Networks are another (cities and roads, computers and cables, people and friendships), and in them only what is joined to what matters. The object that keeps exactly that information is a graph. Algorithms and Data Structures shows how to store and search one; this lesson proves what is true of every graph, using two ideas from Proof and Logic: bijections, and equivalence relations, which cut a set into disjoint classes.

Vertices and edges

A simple graph $G = (V, E)$ is a finite set $V$ of vertices together with a set $E$ of edges, where each edge is a two element subset ${u, v}$ of $V$ . Two vertices joined by an edge are adjacent, or neighbours, and the edge is incident to both. A graph is fully described by its edge list: ${1, 2}, {2, 3}, {3, 1}, {3, 4}$ is a triangle with a tail.

The complete graph $K_{n}$ has $n$ vertices and every possible edge, so it has $(\binom{n}{2}) = \frac{n (n - 1)}{2}$ edges: a round robin tournament among $20$ football clubs is $K_{20}$ with $190$ edges. The cycle $C_{n}$ has vertices $1, \dots, n$ and edges ${1, 2}, {2, 3}, \dots, {n, 1}$ . The complete bipartite graph $K_{m, n}$ has $m$ vertices on one side and $n$ on the other, and every edge joining the two sides, so $m n$ edges. A multigraph also allows several edges between the same two vertices (and loops), so that two bridges between the same banks stay two edges. The river problem needs this; otherwise "graph" means simple graph.

Degree and the handshake lemma

The degree $\deg (v)$ of a vertex is the number of edges incident to it. In $K_{n}$ every vertex has degree $n - 1$ ; in $C_{n}$ every vertex has degree $2$ ; in the triangle with a tail the degrees are $2, 2, 3, 1$ . A graph in which every vertex has the same degree $k$ is $k$ -regular.

Handshake lemma. In any graph, $\sum_{v \in V} \deg (v) = 2 | E |$ .

Count, in two ways, the pairs $(v, e)$ with $e$ an edge incident to the vertex $v$ . Vertex $v$ is in $\deg (v)$ of them, giving the sum on the left; each edge has two ends and is in two of them, giving $2 | E |$ . In the triangle with a tail, $2 + 2 + 3 + 1 = 8 = 2 \times 4$ . At a party, summing the handshakes of every guest counts each handshake twice, hence the name.

Corollary. Every graph has an even number of vertices of odd degree.

The even degrees sum to an even number, so the odd degrees must too, which takes an even number of them. At any party, the number of guests who shook an odd number of hands is even. A degree list with an odd sum belongs to no graph, but an even sum is not enough: no simple graph has degrees $3, 3, 1, 1$ , since on four vertices each vertex of degree $3$ is adjacent to every other, giving the last two degree at least $2$ .

Example. A lab wants to cable $15$ computers so that each is connected directly to exactly $3$ others. Can it be done? And if each is to be connected to exactly $4$ others, how many cables are needed?

With every degree $3$ the degree sum would be $15 \times 3 = 45$ , which is odd, but it must equal $2 | E |$ , so no such network exists. With every degree $4$ the sum is $60$ , so $30$ cables, and a ring joining each computer to the two nearest on either side achieves it.

Now you. A graph has $9$ edges and every vertex has degree $3$ . How many vertices does it have? Could a graph have exactly $7$ vertices, all of degree $3$ ?

Answer

The degree sum is $2 \times 9 = 18$ , and it is also $3 n$ , so $n = 6$ . For $7$ vertices of degree $3$ the sum would be $21$ , which is odd, so no such graph exists.

Isomorphism

The edge list ${a, c}, {c, e}, {e, b}, {b, d}, {d, a}$ draws as a five pointed star, yet renaming $a, c, e, b, d$ as $1, 2, 3, 4, 5$ turns it into exactly $C_{5}$ . Two graphs $G$ and $H$ are isomorphic if there is a bijection $f$ from the vertices of $G$ to the vertices of $H$ such that ${u, v}$ is an edge of $G$ exactly when ${f (u), f (v)}$ is an edge of $H$ . It is a renaming, and isomorphic graphs are, for every question here, the same graph.

Showing two graphs are isomorphic takes one bijection, checked edge by edge. Showing they are not means ruling out all $n!$ bijections at once, and the tool is an invariant, a property every isomorphism preserves: the numbers of vertices and edges, the list of degrees (neighbours of $v$ go one to one onto neighbours of $f (v)$ ), the number of triangles. If one invariant differs, the graphs are not isomorphic; if the ones you tried agree, nothing follows.

Example. The prism $P$ has vertices $a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}$ and edges forming the triangles $a_{1} a_{2} a_{3}$ and $b_{1} b_{2} b_{3}$ together with ${a_{1}, b_{1}}, {a_{2}, b_{2}}, {a_{3}, b_{3}}$ . Show that $P$ is not isomorphic to $K_{3, 3}$ .

The obvious invariants agree: both graphs have $6$ vertices and $9$ edges, and both are $3$ -regular. The prism contains a triangle, $a_{1} a_{2} a_{3}$ . The graph $K_{3, 3}$ contains none: every edge crosses from one side to the other, so any closed route alternates sides and has even length, and a triangle would need three. An isomorphism would carry the prism's triangle to a triangle in $K_{3, 3}$ , so no isomorphism exists.

Now you. Let $G$ be the hexagon $C_{6}$ on vertices $1, \dots, 6$ with the extra edge ${1, 4}$ , and let $H$ be $C_{6}$ with the extra edge ${1, 3}$ . Check that the vertex counts, edge counts and degree lists agree, then show that $G$ and $H$ are not isomorphic.

Answer

Both have $6$ vertices and $7$ edges, and both have degrees $3, 3, 2, 2, 2, 2$ . The graph $H$ contains the triangle $1, 2, 3$ . The graph $G$ has none: no two neighbours of any vertex are adjacent (those of $1$ are $2, 4, 6$ , those of $4$ are $1, 3, 5$ ). So they are not isomorphic.

Walks, paths and connectedness

A walk is a sequence of vertices $v_{0}, v_{1}, \dots, v_{k}$ in which each consecutive pair is an edge; it has length $k$ , the number of edges used, and it is closed if $v_{k} = v_{0}$ . A trail is a walk that uses no edge twice, and a path is a walk that repeats no vertex. A cycle is a closed walk of length at least $3$ whose vertices are distinct apart from the return to the start.

A walk from $u$ to $v$ always contains a path from $u$ to $v$ : in a shortest such walk, a repeat $v_{i} = v_{j}$ with $i < j$ could be cut out to leave a shorter walk, so there is none.

Write $u \sim v$ when there is a walk from $u$ to $v$ . This is an equivalence relation: reflexive by the walk of length $0$ , symmetric because a walk read backwards is a walk, and transitive because a walk from $u$ to $v$ followed by one from $v$ to $w$ is a walk from $u$ to $w$ . Two paths joined end to end may meet and stop being a path, which is why the relation uses walks.

The equivalence classes of $\sim$ are the connected components of the graph. Equivalence classes partition a set, so every vertex lies in exactly one component, and no edge joins two components, since its ends are related. A graph is connected if it has exactly one component. The graph with edges ${1, 2}, {2, 3}, {4, 5}$ on vertices $1, \dots, 6$ has three components, ${1, 2, 3}$ , ${4, 5}$ and ${6}$ .

Deleting an edge that lies on a cycle never disconnects a graph. If ${x, y}$ lies on a cycle, the rest of the cycle is a path from $x$ to $y$ , and any walk that used the edge can take that detour instead.

The bridges of Königsberg

Königsberg, in Prussia (now Kaliningrad), stood where the river Pregel flows round the island of Kneiphof, and seven bridges joined its four land masses. Could a walk cross every bridge exactly once? Leonhard Euler answered in a paper presented to the St Petersburg Academy in 1735 and printed in its volume for 1736, Solutio problematis ad geometriam situs pertinentis.

Euler labelled the island $A$ , the north and south banks $B$ and $C$ , and the eastern land between the two arms of the river $D$ . Two bridges joined $A$ to $B$ , two joined $A$ to $C$ , and one each joined $A$ to $D$ , $B$ to $D$ and $C$ to $D$ . With a vertex per land mass and an edge per bridge, this multigraph has degrees

\deg (A) = 5, \deg (B) = 3, \deg (C) = 3, \deg (D) = 3

and the handshake lemma checks the count: $5 + 3 + 3 + 3 = 14 = 2 \times 7$ .

Euler's multigraph of Königsberg: the island A, the north and south banks B and C, and the eastern land D, with one edge per bridge. Two edges join A to each bank, and single edges join D to A, B and C, so A has degree 5 and the other three have degree 3.

Euler's argument was a count. A route crossing all seven bridges passes through a sequence of eight land masses. A land mass with $k$ bridges, $k$ odd, must appear in that sequence $\frac{k + 1}{2}$ times, since every visit except possibly the first or last uses up two of its bridges. So $A$ appears $3$ times and each of $B$ , $C$ , $D$ appears $2$ times, which is $9$ appearances in a sequence of $8$ . No such walk exists. Euler saw that only the parity of the degrees mattered and stated the general rule, but the proof that the right parities guarantee a walk came 137 years later.

Euler's theorem

An Euler trail uses every edge of the graph, and an Euler circuit is a closed one.

Theorem. A connected multigraph has an Euler circuit exactly when every vertex has even degree. It has an Euler trail that is not closed exactly when it has exactly two vertices of odd degree, and then every such trail starts at one of them and ends at the other.

Necessity. Each pass of an Euler circuit through a vertex arrives along one edge and leaves along another, and the first departure pairs with the final arrival. Every edge is used once, so the edges at each vertex split into pairs and every degree is even. On a trail from $u$ to $v \neq u$ the first edge at $u$ and the last at $v$ are left unpaired, so exactly $u$ and $v$ are odd. Königsberg, with four odd vertices, has neither.

Sufficiency. Suppose every degree is even. Start at a vertex $v$ and walk, never reusing an edge, until stuck. Arriving at any $w \neq v$ , the walk has used an odd number of edges at $w$ (a pair per earlier pass plus the one just used), and $\deg (w)$ is even, so it can leave again. So it gets stuck only at $v$ , as a closed trail $T$ . If $T$ misses some edges, some vertex $u$ of $T$ has an unused edge, since otherwise nothing would join $T$ to the unused edges and the graph would be disconnected. The unused edges still have even degree at every vertex, because $T$ used an even number at each, so the same argument builds a closed trail $T^{'}$ from $u$ out of them. Splice it in: follow $T$ to $u$ , go round $T^{'}$ , finish $T$ . The closed trail is longer, and repeating uses every edge. This is Carl Hierholzer's argument, published in 1873, two years after his death.

For two odd vertices $u$ and $v$ , add a new edge ${u, v}$ (a multigraph allows it). Every degree is now even, so there is an Euler circuit, and deleting the new edge from it leaves an Euler trail between $u$ and $v$ .

Example. Find an Euler circuit of $K_{5}$ .

Every degree is $4$ , so one exists. Start at $1$ and walk $1, 2, 3, 1$ until stuck. Vertex $1$ has unused edges, so walk from it: $1, 4, 2, 5, 1$ . Splice at $1$ to get $1, 4, 2, 5, 1, 2, 3, 1$ . The edges ${3, 4}, {4, 5}, {5, 3}$ remain, forming the closed trail $3, 4, 5, 3$ , and vertex $3$ is on the circuit, so splice at $3$ :

1, 4, 2, 5, 1, 2, 3, 4, 5, 3, 1

That is ten edges, all different, and $K_{5}$ has $(\binom{5}{2}) = 10$ .

Now you. German children draw das Haus vom Nikolaus in one stroke without lifting the pen. It is the graph with edges ${1, 2}, {2, 3}, {3, 4}, {4, 1}, {1, 3}, {2, 4}, {3, 5}, {4, 5}$ : a square with both diagonals and a roof. Where must the drawing start, and what is one way to draw it?

Answer

The degrees are $\deg (1) = 3$ , $\deg (2) = 3$ , $\deg (3) = 4$ , $\deg (4) = 4$ , $\deg (5) = 2$ . Exactly two are odd, so an Euler trail exists and it must start at $1$ or $2$ and end at the other. One is $1, 2, 3, 4, 1, 3, 5, 4, 2$ , which uses all eight edges once.

Hamilton's question

Change one word: instead of every edge once, ask for a cycle through every vertex once. Such a cycle is a Hamilton cycle, after William Rowan Hamilton, who in 1857 invented the icosian game: find a route along the edges of a dodecahedron through all twenty of its corners, returning to the start. He sold it to a London games maker in 1859 for £25. The puzzle is not hard, but the question behind it has never been answered as Euler answered his.

Euler's criterion is one pass over the degrees. Deciding whether a graph has a Hamilton cycle is NP-complete (one of Richard Karp's 1972 list), so no efficient test is known, and finding one would settle the P versus NP problem. What exists instead are sufficient conditions.

Dirac's theorem (1952). A simple graph with $n \geq 3$ vertices in which every vertex has degree at least $\frac{n}{2}$ has a Hamilton cycle.

The bound cannot be lowered. Take $K_{k, k + 1}$ , with $n = 2 k + 1$ vertices and smallest degree $k$ , just below $\frac{n}{2}$ . A cycle alternates sides, so it visits equally many vertices on each, and cannot visit all $k + 1$ on the larger side. The condition is also far from necessary: $C_{100}$ is itself a Hamilton cycle, with every degree $2$ .

Cycles are where the difficulty lives, and they are also what a connected graph can spare: since deleting an edge on a cycle never disconnects a graph, any connected graph can be stripped, one cycle edge at a time, to a connected graph with no cycles at all. Those are the simplest connected graphs, and the next lesson studies them as trees.