COMP2121 Chap.9 Graphs, Isomorphism and Euler Circuits
Graphs, Isomorphism and Euler Circuits
Graph vocabulary and counting degrees
A graph is a set of vertices and edges, simple unless stated otherwise. The handshaking theorem says the degrees sum to twice the number of edges, so every graph has an even number of odd vertices.
Complete graphs, cycles, wheels and complete bipartite graphs have edge counts by formula, and bipartite graphs are exactly those without odd cycles.
Isomorphism and Euler circuits
Isomorphism is shown with an adjacency-preserving bijection and refuted with a differing invariant.
A connected graph has an Euler circuit exactly when every degree is even, and an Euler path that is not a circuit exactly when two vertices are odd.
Formulas for the standard families
The complete graph on n vertices has n times n minus 1 over 2 edges and every degree equal to n minus 1. A cycle on n vertices has n edges, a wheel adds a hub joined to every cycle vertex, and the complete bipartite graph on m and n vertices has m times n edges.
The n-cube has two to the n vertices, each of degree n. These counts, combined with the handshaking theorem, settle most existence questions about degree lists quickly.
Why the Euler test works
Every time a circuit passes through a vertex it uses two of its edges, so every degree in a graph with an Euler circuit must be even.
For the converse, start anywhere and walk without reusing edges until you return; if edges remain, start a second circuit at a vertex already visited and splice it in. Repeating the splice uses every edge, provided the graph is connected, which is why connectivity is always checked first.
What this chapter covers
- 01
Vertices, edges and degree
- 02
Handshaking theorem
- 03
Complete, cycle, wheel and bipartite graphs
- 04
Isomorphism and invariants
- 05
Connectivity
- 06
Euler paths and circuits
Worked example · free
Count edges from degrees
- 2Sum the degrees and halve the total.
- 1Count the odd-degree vertices.
- 2Apply the Euler test.
Key terms
- Degree
- The number of edges incident with a vertex.
- Bipartite graph
- A graph whose vertices split into two sides with every edge crossing between them.
- Graph isomorphism
- A bijection between vertex sets that preserves adjacency.
- Euler circuit
- A circuit that uses every edge of a graph exactly once.
Graphs, Isomorphism and Euler Circuits FAQ
Why is the degree sum always even?
Each edge has two endpoints, so it adds two to the sum of degrees. The sum is therefore twice the number of edges, and the number of odd-degree vertices must be even.
How do I prove two graphs are not isomorphic?
Find an invariant on which they differ, such as the degree list, the number of triangles or connectivity. Matching invariants never prove isomorphism; that needs an explicit bijection.
When does a graph have an Euler path but no circuit?
When it is connected and exactly two vertices have odd degree. The path must start at one of them and finish at the other. A closed walk through every edge is impossible in that case.
Which complete graphs have an Euler circuit?
The complete graph on n vertices has every degree equal to n minus 1, so it has an Euler circuit exactly when n is odd. For example, the complete graph on five vertices has one and the complete graph on four does not.
How do I test whether a graph is bipartite?
Try to two-colour it: give one vertex a colour, give its neighbours the other colour, and continue. The graph is bipartite exactly when this never forces two adjacent vertices to share a colour, which happens precisely when the graph has no cycle of odd length.
Exam move
Practise reading degree lists, edge counts and Euler verdicts for complete, cycle, wheel and complete bipartite graphs. For isomorphism, list invariants before searching for a bijection. Reproduce the splicing construction for Euler circuits on a small graph so the sufficiency proof is something you have done, not only read.
Draw each standard family for small sizes and label the degrees, so every edge count can be checked against the handshaking theorem. For isomorphism questions, record degree lists, cycle lengths and connectivity in a small table before attempting any matching.
Working through Graphs, Isomorphism and Euler Circuits in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Graphs, Isomorphism and Euler Circuits question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.