The Lumenary · Grades 9–12

Graphs

Name: ______________________

Date: ______________________

You will learn to

Model networks with graphs and use the vocabulary of vertices, edges, degrees, walks, paths, cycles and connectedness
Prove the handshake lemma and deduce that every graph has an even number of vertices of odd degree
Prove Euler's theorem that a connected graph has an Euler circuit exactly when every vertex has even degree, and its version for Euler trails
Prove that a tree with $n$ vertices has $n - 1$ edges and that any two of its vertices are joined by exactly one path
Decide whether two small graphs are isomorphic, using invariants to prove that they are not

1.
A graph has seven vertices, with degrees $3, 3, 2, 2, 2, 1, 1$ . How many edges does it have?
2.
Can there be a group of $7$ people in which every person knows exactly $3$ of the others (knowing being mutual)?
- A.No: the numbers of acquaintances would add up to $7 \times 3 = 21$ , which is odd, but they must add up to twice the number of pairs who know each other.
- B.Yes: arrange the $7$ people in a circle and let each know their neighbours and the person opposite.
- C.No, because $3$ is more than half of $7$ .
- D.Yes, but only if one person knows nobody.
3.
An engineering cooperative lays water pipes to connect $50$ villages in a region of Bolivia so that water can flow between any two villages, using as few pipes as possible: the network has no loops. Each pipe joins two villages. How many pipes are there?
4.
A connected graph has six vertices with degrees $2, 4, 3, 3, 4, 2$ . Which statement is true?
- A.It has an Euler trail that starts at one vertex of degree $3$ and ends at the other, but no Euler circuit.
- B.It has an Euler circuit.
- C.It has no Euler trail at all.
- D.Such a graph cannot exist, because the degrees add up to an odd number.
5.
The cube graph has the $8$ corners of a cube as vertices and its $12$ edges as edges. Which statements are true? (Choose all that apply.)
- A.It has a Hamiltonian cycle (a cycle visiting every vertex exactly once).
- B.It has an Euler circuit.
- C.It has no Euler trail.
- D.It has $\frac{8 \times 3}{2} = 12$ edges, consistent with the handshake lemma.
6.
To prove that a tree with at least two vertices has a leaf, we take a longest path $v_0, v_1, \dots, v_k$ and show that $v_k$ is a leaf. Why can $v_k$ have no neighbour other than $v_{k-1}$ ?
- A.A neighbour outside the path would give a longer path, and a neighbour $v_i$ with $i < k - 1$ would close a cycle.
- B.Because a tree with $n$ vertices has $n - 1$ edges.
- C.Because the degrees add up to twice the number of edges.
- D.Because $v_k$ was chosen to have the smallest degree.
7.
How many trees with $5$ vertices are there up to isomorphism — that is, how many different shapes?
8.
In the lesson's Lean model, IsEulerCircuit G w says that the walk w crosses every edge of the multigraph G exactly once and ends where it started. Which statement is a correct formalisation of the necessity half of Euler's theorem for circuits?
- A.IsEulerCircuit G w → ∀ v, Even (degree G v)
- B.(∀ v, Even (degree G v)) → ∃ w, IsEulerCircuit G w
- C.IsEulerCircuit G w → ∃ v, Even (degree G v)
- D.IsEulerCircuit G w → ∀ v, Odd (degree G v)
9.
A connected multigraph on the vertices $0, 1, \dots, n - 1$ is given as a list of edges (a, b) (pairs may repeat). Write euler_status(n, edges) that returns "circuit" if it has an Euler circuit, "trail" if it has an Euler trail but no circuit, and "none" otherwise, using Euler's theorem. (Assume at least one edge.)
Computational — Practice

Answer key — Graphs

1.
The degrees add up to $14$ , and by the handshake lemma this is $2|E|$ . So $|E| = 7$ .
2.
In the acquaintance graph every vertex would have degree $3$ , so the degrees would add up to $21$ . But by the handshake lemma the sum of the degrees is $2|E|$ , an even number. So no such group exists. (Equivalently: a graph cannot have an odd number — here $7$ — of odd-degree vertices.)
3.
The network is connected and has no cycles, so it is a tree with $50$ vertices. By Theorem 6 it has $50 - 1 = 49$ edges, that is $49$ pipes — however the pipes are arranged.
4.
The odd degrees are the two $3$ s, so exactly two vertices have odd degree. Since the graph is connected, Euler's theorem gives an Euler trail from one of them to the other; and since not every degree is even, there is no Euler circuit.
5.
Every vertex has degree $3$ , so the degree sum is $24 = 2 \times 12$ (d). All eight degrees are odd, so there is neither an Euler circuit nor an Euler trail (b false, c true). A Hamiltonian cycle exists (a): top face, down, bottom face in reverse, up. Euler circuits (every edge once) and Hamiltonian cycles (every vertex once) are different questions.
6.
If $v_k$ had a neighbour $x$ not on the path, then $v_0, \dots, v_k, x$ would be a longer path, contradicting the choice. If it had a neighbour $v_i$ with $i < k - 1$ , then $v_i, v_{i+1}, \dots, v_k, v_i$ would be a cycle, impossible in a tree. So $v_{k-1}$ is its only neighbour, and $v_k$ is a leaf.
7.
A tree on $5$ vertices has $4$ edges, so the degrees add up to $8$ , and each degree is at least $1$ . If the largest degree is $4$ , the tree is the star (degrees $4, 1, 1, 1, 1$ ). If it is $2$ , the tree is the path (degrees $2, 2, 2, 1, 1$ ). If it is $3$ , the degrees are $3, 2, 1, 1, 1$ : a vertex with three branches, one of which has length $2$ — a single shape. These three have different degree sequences, so they are pairwise non-isomorphic: there are $3$ shapes. (The computation section confirms this by checking all $125$ labelled trees.)
8.
Statement (a): if w is an Euler circuit of G then every vertex has even degree. Statement (b) is the converse, which needs connectedness; (c) is too weak; (d) is false.

def euler_status(n, edges):
    deg = [0] * n
    for a, b in edges:
        deg[a] += 1
        deg[b] += 1
    odd = sum(d % 2 for d in deg)
    if odd == 0:
        return "circuit"
    if odd == 2:
        return "trail"
    return "none"

By the handshake lemma the number of odd vertices is always even, so the cases $0$ , $2$ and " $4$ or more" cover everything. The answer relies on the graph being connected, as Euler's theorem requires.