Maths › Decision Mathematics 1 › Graphs: order, Eulerian paths and planarity
Graphs: order, Eulerian paths and planarity
The vocabulary the rest of the paper runs on, plus one theorem worth its weight: counting odd nodes settles whether a network can be walked without repeating an edge.
Builds on Algorithms, sorting and bin packing and The structure of proof.
IN THIS TOPIC
- Find the order of every node and use it to classify a graph.
- Recognise complete, planar, isomorphic and Hamiltonian structures.
- Apply the planarity algorithm to a Hamiltonian graph.
COMMON MISCONCEPTION
A graph with an even number of odd nodes has an Eulerian circuit.
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 real test is how many odd nodes there are, counted on a connected graph: isolated nodes may be ignored, but the edges must all hang together, or no single trail can reach them. None, and the graph is Eulerian, meaning a closed trail exists that uses every edge exactly once. Exactly two, and it is semi-Eulerian, with such a trail starting at one odd node and ending at the other. More than two, and no such trail exists at all. That is the problem the route inspection algorithm later sets out to fix.
WORKED EXAMPLE
Classifying a network
In the network shown, the orders are A 3, B 3, C 4, D 3, E 3 and F 2. Classify it.
The orders total 18, which is twice the nine edges, as it must be.
Four nodes are odd: A, B, D and E.
Four is more than two, so the graph is neither Eulerian nor semi-Eulerian: no route can use every edge exactly once.
Complete, planar and isomorphic
A complete graph Kn 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, one visiting every node exactly once. 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 clashes can be split into an inside group and an outside group, the graph is planar; if they cannot, it is not. K5 and K3,3 always fail, and Kuratowski's theorem says a graph is non-planar precisely when it contains a subdivision of one of them.
GUIDED PRACTICE
Testing a graph for planarity
Explain how you would test whether a graph containing a Hamiltonian cycle is planar, and why K5 fails.
Show the working
Redraw the Hamiltonian cycle as a circle with the remaining edges as chords.
Work through the chords, placing each inside or outside, and record which pairs would cross if they shared a side.
If every chord can be placed the graph is planar; if some chord clashes with whatever is on both sides, it is not.
Take K5 with the cycle ABCDEA. That uses five of the ten edges, leaving the chords AC, AD, BD, BE and CE.
Each chord clashes with exactly two of the others: AC with BD and BE, BD with CE, CE with AD, and AD with BE. Those clashes chain into a loop of five, and a loop of odd length cannot be split into two clash-free groups, so one chord always has nowhere to go.
ASSESSMENT FOCUS
- List the orders of all the nodes before saying anything about Eulerian trails.
- Check the orders total twice the number of edges. It catches a miscount immediately.
- For isomorphism, match the orders and then give the correspondence explicitly.
- For planarity, name the Hamiltonian cycle you are using and set the working out as a table of chords.
CHECK YOURSELF
A connected graph has nodes of order 2, 3, 3, 4 and 4. Is it Eulerian, semi-Eulerian or neither?
Show a hint
Count the odd nodes.
Show the answer
Two nodes are odd, so it is semi-Eulerian: a trail using every edge once exists, starting at one odd node and finishing at the other.
The orders always total twice the number of edges, so the number of odd nodes is always even.
For a connected graph, no odd nodes means Eulerian, exactly two means semi-Eulerian, and more than two means neither.
The planarity algorithm needs a Hamiltonian cycle: draw it as a circle and try to split the chords between inside and outside.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the graphs: order, eulerian paths and planarity questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Find the order of every node and use it to classify a graph.
- Recognise complete, planar, isomorphic and Hamiltonian structures.
- Apply the planarity algorithm to a Hamiltonian graph.
Open the full revision checklist to see every objective in the course in one place.