D1 1.3 - Graph terminology and Eulerian graphs
You will describe graphs accurately, count node orders, decide whether every arc can be traced exactly once, and recognise complete, planar and isomorphic graphs.
Nodes, arcs and routes
Can you draw a connected graph in one continuous stroke, tracing every arc exactly once, if it has four odd-order nodes? The answer depends on the connections, not on how neatly the graph is drawn. We will develop a counting test that settles it without trying every possible route.
You already know
An even integer is divisible by ; an odd integer is not. Adding two odd integers gives an even integer. No earlier Decision Mathematics topic is needed here.
A graph records which objects are linked. Its nodes might represent towns and its arcs roads, but lengths and angles on the page have no significance unless information is supplied. The following graph includes both parallel arcs and a loop.
[DIAGRAM: asset_name: 9fm0-d1-164-loops-and-parallel-arcs.png; asset_slug: 9fm0-d1-164-loops-and-parallel-arcs; caption: A graph with two arcs joining A and B, and a loop at D.; description: Four nodes A, B, C and D with arcs AB twice, BC, CA, CD and DD; the two AB arcs are separately visible and the loop at D has both ends attached to D.]
Graph vocabulary
A node or vertex is a point of a graph. An arc or edge joins two nodes. Adjacent nodes are joined by an arc. A loop joins a node to itself; parallel arcs join the same pair of nodes.
A simple graph has neither loops nor parallel arcs. A connected graph has a path between every pair of nodes. A tree is a connected undirected graph with no cycles.
Two arcs that cross on paper are not joined unless a node is marked at the crossing. In a directed graph, arrows restrict travel; here our graphs are undirected. A network is a graph with numerical information, such as weights on its arcs.
Different route words impose different restrictions. In particular, visiting a node twice is not the same as using an arc twice.
| Route | Restriction |
|---|---|
| Walk | A sequence of adjacent nodes; nodes and arcs may repeat |
| Trail | No arc is repeated |
| Path | No node is repeated |
| Closed walk | Starts and ends at the same node |
| Circuit | A closed trail |
| Cycle | A closed path: only the first and last node are repeated |
For example, on the pictured graph is a cycle. The walk is a trail if it uses the two different arcs, but not if it immediately retraces the same one. Record which arc is used when parallel arcs matter.
Key idea
Read a graph by its nodes and connections. Crossings, arc lengths and the positions of the nodes do not change its structure.
Use the distinction between repeating a node and repeating an arc.
Node orders and the handshaking result
To count the order of a node, count arc ends meeting it. The loop at has two ends at , so it contributes two, not one.
Order or degree of a node
The order, degree or valency of a node is the number of incident arc ends, counting a loop twice and each parallel arc separately. A node is odd or even according to its order.
Every arc contributes two to the total of all node orders: one at each end, or both at the same node for a loop. This is the handshaking argument.
Counting arc ends
For an undirected graph with arcs,
Consequently, the number of odd-order nodes is even.
A tree with nodes has arcs, so its node orders sum to .
Not in the formula booklet: learn it.
The parity conclusion is surprisingly strong: no undirected graph can have exactly one, three or five odd nodes, however many loops or parallel arcs you add. For the tree count, start with one node and add a new node with one joining arc at a time; each addition preserves connectedness without creating a cycle.
Worked example 1: loops and parallel arcs
Question. A graph has nodes and arcs . Find each node's order and the number of odd nodes.
Plan. Count incident arc ends at each node, treating the two arcs separately and counting twice.
| Node | Contributions | Order |
|---|---|---|
| Two arcs and | ||
| Two arcs and | ||
| and two ends of |
Why count the loop twice? Both of its ends meet ; it supplies two incident arc ends.
Answer. All four nodes have order , so there are odd nodes.
Check. The sum is , twice the number of arcs.
Worked example 2 adds only the arc . Only its two endpoints change order.
Worked example 2: adding an arc
Question. Add to the previous graph. Find its node orders and the number of odd nodes.
Plan. Increase the orders of and by one; retain the orders of and .
Why do two parities change? An added non-loop arc contributes one end to each of two different nodes.
Answer. There are odd nodes, and .
Check. The total is , consistent with one extra arc.
The sum check detects many counting slips, but it cannot prove that an arbitrary proposed degree sequence is realisable. For example, a simple graph has the additional restriction that a node can meet each other node at most once.
Watch out
Wrong: a graph with nodes always has node orders at most . Right: this restriction applies to a simple graph. Loops and parallel arcs can give larger orders.
Change the endpoints of the added arc in the matched check.
Eulerian and semi-Eulerian graphs
Imagine entering a node along an unused arc and leaving along another. At every node other than the route's endpoints, the used arc ends pair up. A closed route has no unpaired endpoints; an open route has exactly two.
Eulerian and semi-Eulerian
An Eulerian graph has a circuit using every arc exactly once. A semi-Eulerian graph has an open trail using every arc exactly once: its start and finish are different.
These definitions allow repeated nodes. They do not allow a repeated arc. For connected undirected graphs, counting odd nodes gives a complete test.
Eulerian classification
For a connected undirected graph with at least one arc:
| Number of odd nodes | Classification |
|---|---|
| Eulerian; a circuit can start at any node | |
| Semi-Eulerian; the odd nodes are the start and finish | |
| or more | Neither Eulerian nor semi-Eulerian |
Not in the formula booklet: learn it.
Why is the condition sufficient as well as necessary? With all orders even, a trail following unused arcs cannot get stuck away from its start. If arcs remain, connectedness lets another closed trail be joined into it. With exactly two odd nodes, temporarily join them with an extra arc, find the circuit, then remove that extra arc to leave the required open trail.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account