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.
WHAT YOU PROBABLY THINK
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. Since every edge contributes to two nodes, the orders always add to twice the number of edges, and the number of odd nodes is therefore always even. That is why the opening claim is empty: every graph has an even number of odd nodes, so the condition rules nothing out.
The real test is how many odd nodes there are. None, and the graph is Eulerian: a closed trail exists using 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. Any more, and no such trail exists, which 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, and two graphs are isomorphic if one can be relabelled into the other, which needs matching numbers of nodes, edges and orders, though those alone are not enough to prove it.
The planarity algorithm works on a graph with a Hamiltonian cycle, one visiting every node exactly once. Redraw that cycle as a circle, then place each remaining edge either inside or outside. Any edge that will not fit on either side without a crossing proves the graph non-planar. K5 and K3,3 are the two that always fail.
YOUR TURN
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 cannot lie on the same side.
If every chord can be placed the graph is planar; if two chords conflict on both sides it is not.
For K5 the cycle uses five of the ten edges, leaving five chords. Any two of them cross, so at most two can go inside and two outside, and the fifth has nowhere to go.
THE EXAM BIT
- 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.
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
T
w
o
n
o
d
e
s
a
r
e
o
d
d
,
s
o
i
t
i
s
s
e
m
i
-
E
u
l
e
r
i
a
n
:
a
t
r
a
i
l
u
s
i
n
g
e
v
e
r
y
e
d
g
e
o
n
c
e
e
x
i
s
t
s
,
s
t
a
r
t
i
n
g
a
t
o
n
e
o
d
d
n
o
d
e
a
n
d
f
i
n
i
s
h
i
n
g
a
t
t
h
e
o
t
h
e
r
.
The orders always total twice the number of edges, so the number of odd nodes is always even.
No odd nodes means Eulerian, exactly two means semi-Eulerian, and more than two means neither.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- 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.
No animated video for this topic yet; these notes stand alone.