Graphs: order, Eulerian paths and planarity

Counting the odd nodes

The order or degree of a node is the number of edges meeting it. Every edge contributes to two nodes, so the orders always add to twice the number of edges, and the number of odd nodes is therefore always even. Every graph satisfies that condition, so it rules nothing out.

The test is the number of odd nodes, and it applies to a connected graph with at least one edge. Isolated nodes may be ignored, but every edge must lie in one connected part, since no single trail can reach two separate parts.

For such a graph: zero odd nodes and the graph is Eulerian, meaning a closed trail, or Eulerian circuit, exists that uses every edge exactly once. Exactly two odd nodes and it is semi-Eulerian, with an Eulerian trail starting at one odd node and ending at the other. More than two and no such trail exists. Route inspection addresses the case of more than two odd nodes.

The parity count alone is insufficient if the non-isolated part of the graph is disconnected: two separate triangles have no odd nodes and no Eulerian circuit.

Loops, multiple edges and simple graphs

Two features not present in the drawings so far carry names of their own. A loop is an edge joining a node to itself, and it adds two to that node's order, since both of its ends meet the same node. Multiple edges are two or more edges joining the same pair of nodes, which is what a model produces as soon as two roads run between the same pair of towns. A graph with neither is simple, and a simple graph that is connected is simply connected, written simple-connected on some papers.

Being simple restricts the orders. With loops and repeats excluded, a node of a simple graph on n nodes can join at most the other n − 1, so no order passes n − 1, and the number of edges rises no higher than n(n − 1)/2, which the complete graph achieves. Connectedness pushes from the other side: each node needs an order of at least 1, and a tree, being connected on as few edges as possible, has at least two nodes of order 1 at the ends of its longest path.

A subgraph is made from some of the nodes and some of the edges of a graph, an edge surviving only when both its ends survive. Deleting a loop and one of a pair of multiple edges leaves a simple subgraph on the same nodes, and a spanning tree is a subgraph too. Dropping a new node of order 2 into the middle of an edge, so that one edge becomes two, is a subdivision, which changes the drawing without changing what is joined to what. That is why the planarity theorem below is stated up to subdivisions.

The operation that runs the other way is contraction. To contract the edge AB, squeeze its two ends together into a single node, written (AB), and let every edge that met A or met B meet (AB) instead. The edge AB itself vanishes into the new node, so the node count falls by one and the edge count falls by one with it, and the order of (AB) is the orders of A and B added and then reduced by two. Where the two nodes being merged are not joined there is no edge to lose, and the order of (AB) is then the two orders added. Contracting several times in turn is allowed and the brackets nest, so contracting (AB) with C next gives (ABC).

Contraction can cost a graph its simplicity, which is the part a question tests. If A and B had a neighbour in common, its two edges both survive and now join the same pair of nodes, so a multiple edge appears; if A and B were joined by two edges, the second becomes a loop at (AB).

Describe the drawing

The unit's six-node network on the left with the edge AB picked out in amber, and on the right the same network after that edge has been contracted. A and B have become a single node written (AB), the edge between them has vanished, and every edge that ran to A or to B now runs to (AB). Four such edges survive, so (AB) has order 4, and because C was joined to both A and B it is now joined to (AB) by two separate edges, drawn in coral as a pair of arcs. Five nodes and eight edges remain, and the doubled pair means the contracted graph is no longer simple.

Walks, trails, paths and cycles

Four words describe travel through a graph, and they differ only in what may be repeated. A walk is a sequence of edges with each one starting where the last finished. A trail is a walk with no edge used twice. A path is a trail with no node visited twice. A cycle is a closed path, finishing at the node it set out from. Route is the loose word for any of these, open or closed.

So an Eulerian trail uses each edge once and may pass a node several times, while a Hamiltonian cycle visits each node once and may leave edges unused.

Putting arrows on the edges turns a graph into a digraph, or directed graph, whose edges are arcs with one permitted direction each. A node then has an indegree, the number of arcs arriving, and an outdegree, the number leaving, and the two totals over the whole digraph agree, since both count the arcs once each. A walk in a digraph follows the arrows. Activity networks and flow networks later in this unit are digraphs, which is why an arc there offers one direction of travel rather than two.

Hamiltonian cycles and Ore's theorem

A Hamiltonian path visits each node of a graph once and once only. A Hamiltonian cycle is such a path that closes, finishing at the node it set out from, and a graph carrying one is a Hamiltonian graph. Edges may be left unused, which is what separates this from the Eulerian question, where the edges are the things being used up and a node may be passed several times.

The Eulerian question was settled by counting odd nodes. Nothing that cheap is known for this one: deciding whether a Hamiltonian cycle is there is one of the problems for which no quick method has been found, so a question either exhibits a cycle or argues that none exists.

Ore's theorem is a condition that settles the question one way without anybody finding a cycle. Take a simple graph on n nodes with n ≥ 3, and look only at the pairs of nodes with no edge between them. If deg v + deg w ≥ n for every such pair v, w, the graph is Hamiltonian. A graph with a good many edges has few pairs to check, since a joined pair is not part of the test, and the test itself is arithmetic on the orders.

In particular, if no node has order below n/2, any two orders total at least n, so the condition holds without a pair being looked at.

The condition is sufficient and not necessary: meeting it settles the question, and failing it settles nothing at all. The five-node cycle A B C D E A is the extreme case. It is a Hamiltonian cycle itself, so the graph is Hamiltonian beyond argument, yet each node has order 2 and an unjoined pair totals 4, well under n = 5.

The unit's own network makes the same point in exam shape. Its orders are A 3, B 3, C 4, D 3, E 3 and F 2, and A and F are not joined, with orders totalling 5 against n = 6, so Ore's condition fails there. All the same, A B E F D C A uses AB, BE, EF, FD, CD and AC and visits each of the six nodes once, so the network is Hamiltonian.

Complete, planar and isomorphic

A complete graph K_n joins every pair of nodes, so it has n(n − 1)/2 edges. A graph is planar if it can be drawn with no edges crossing. Two graphs are isomorphic if one can be relabelled into the other, which needs matching numbers of nodes, edges and orders, though matching those does not by itself prove it. Give the correspondence.

The planarity algorithm works on a graph that contains a Hamiltonian cycle, so find one first. Redraw that cycle as a circle with the remaining edges as chords, then place each chord inside or outside. Two chords clash when they would cross on the same side. If the chords can be split into an inside group and an outside group with no clash in either, the graph is planar; if they cannot, it is not. K₅ and K_3,3 always fail, and Kuratowski's theorem says a graph is non-planar precisely when it contains a subdivision of one of them.

Describe the drawing

On the left, five nodes each joined to all the others, drawn as a pentagon with its diagonals. On the right, two rows of three nodes with every node in one row joined to every node in the other. Neither can be redrawn without lines crossing, and Kuratowski's theorem says a graph is non-planar precisely when it contains a subdivision of one of these two.

Bipartite graphs and complements

A graph is bipartite when its nodes can be split into two groups with each edge running between the groups and none inside either. The complete bipartite graph K_m,n joins each of m nodes to each of n nodes, so it has mn edges, and the K_3,3 of the last section is the case m = n = 3 with its nine edges.

To test a graph, colour any node, colour its neighbours in the second colour, and carry on. A conflict, two nodes of one colour joined by an edge, shows that no split exists; a colouring that reaches the last node is the split, one colour on each side. What breaks the test is a cycle of odd length, since going round such a cycle returns to the starting node on the wrong colour, and a graph free of odd cycles passes it.

The complement of a graph on n nodes has the same nodes and the edges the graph lacks: draw K_n and rub out whatever the graph already carries. The two edge counts therefore add to n(n − 1)/2, and a node of order d in one has order n − 1 − d in the other. A question about the pairs of towns with no road between them is a question about the complement.

Counting the regions

A planar drawing cuts the page into regions, also called faces, and the unbounded region outside the drawing counts as one of them. Count the nodes V, the edges E and the regions R of a connected planar drawing and V − E + R = 2 comes out, whichever drawing was made. That is Euler's formula, and redrawing the graph shuffles the regions about without changing how many there are, so the count belongs to the graph and not to the picture.

Here is why. Start from a spanning tree, which has V nodes, V − 1 edges and one region, so the count reads V − (V − 1) + 1 = 2. Putting back any other edge closes a cycle and so divides one region in two, raising E by one and R by one and leaving V − E + R where it was. Restore the edges one at a time and the whole graph is reached with the count untouched.

The formula bounds how many edges a planar graph can carry. In a simple graph each region is bounded by three edges or more, and counting each edge once for each of its two sides gives 2E ≥ 3R. Substituting R = 2 − V + E and tidying leaves E ≤ 3V − 6 for a simple connected planar graph on three or more nodes. A bipartite graph has no triangle, so its regions need four edges or more, 2E ≥ 4R, and the bound tightens to E ≤ 2V − 4.

That settles both obstructions without drawing a single chord. K₅ has V = 5 and E = 10, against a bound of 3V − 6 = 9, so it fails and no plane drawing of it exists. K_3,3 has V = 6 and E = 9 and is bipartite, so the tighter bound applies: 2V − 4 = 8, and nine edges is one too many. The reasoning runs one way only, since a graph that passes the bound may still be non-planar, and that is what Kuratowski's theorem is for.

Splitting a graph into planar layers

A graph that admits no plane drawing can still be drawn in layers. The thickness of a graph is the least number of planar subgraphs its edges can be split between, each edge going into one layer and each layer drawn without a crossing. Thickness 1 is planarity itself. Thickness 2 says the edges can be shared out between two sheets, each of them flat, which is the question a circuit board with conducting material on both faces asks.

Euler's bound says how few layers might do. A layer is a simple graph on the same V nodes, so it carries at most 3V − 6 edges, and t layers between them carry at most t(3V − 6). A graph with E edges therefore needs at least E/(3V − 6) layers, rounded up. Where the graph is bipartite the tighter bound 2V − 4 governs each layer instead, since a subgraph of a bipartite graph is bipartite.

That bound is a floor and a split of the edges is a ceiling, and where the two meet the thickness is settled. Questions at this level stop at two: decide whether one layer will do, and where it will not, produce the two layers. Finding a thickness above two is another matter and is not asked for.

K_3,3 is settled as easily, using the bipartite bound. It has V = 6 and E = 9, and no layer of it carries more than 2V − 4 = 8 edges, so one layer is short by an edge and its thickness is above 1. With its sides labelled A, B, C and X, Y, Z, take out any single edge, say CZ, and what is left is planar: A and B joined to each of X, Y and Z gives three paths from A to B drawn side by side, and C, which now meets X and Y only, sits in the region between two of those paths. So the thickness of K_3,3 is 2 as well: neither of Kuratowski's two obstructions fits on one sheet, and both fit on two.