Eulerian and Hamiltonian graphs Problem set A One question at a time

Show that the graph is semi-Eulerian and find an Eulerian trail.

• Degrees: P 2, Q 2, R 4, S 1, T 3, U 2
• Exactly two vertices are odd, S and T: semi-Eulerian
• Start at S, finish at T: S-R-P-T-Q-R-U-T
• Check that every edge is used once

Show that the graph is Eulerian and find an Eulerian circuit.

• Degrees: A 4, B 4, C 4, D 2, E 2, F 2, G 2, H 2
• Every degree is even: Eulerian
• Start anywhere, for example A: A-B-C-D-A-E-H-C-G-B-F-A
• The circuit returns to its start and uses every edge once

Explain why the graph is not Eulerian. Is it semi-Eulerian?

• Degrees: A 4, B 3, C 3, D 3, E 2, F 3
• Odd vertices: B, C, D, F, which is 4
• An Eulerian circuit needs 0 odd vertices and an Eulerian trail needs exactly 2
• There are 4, so there is neither

Which of these adjacency matrices represent Eulerian graphs? \(M_1=\begin{pmatrix}0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0\end{pmatrix}\), \(M_2=\begin{pmatrix}0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0\end{pmatrix}\), \(M_3=\begin{pmatrix}0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\)

• M_1: row sums 4, 2, 4, 4, 2, 2 (all even)
• M_2: row sums 3, 3, 3, 3, 3, 3 (some odd)
• M_3: row sums 2, 2, 2, 2 (all even)
• Eulerian when every row sum is even: M_1, M_3

A graph has vertices P, Q, R and S in this order and adjacency matrix \(A=\begin{pmatrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\)

1. (a) Draw the graph.

   • A 1 in row i and column j means an edge ij. Edges: PQ, QR, RS, SP, PR
   • Draw the vertices in the order of the rows and join these pairs

2. (b) Find the number of walks of length 5 from P to R.

   • From the calculator: \(A^5=\begin{pmatrix}32 & 29 & 33 & 29 \\ 29 & 18 & 29 & 18 \\ 33 & 29 & 32 & 29 \\ 29 & 18 & 29 & 18\end{pmatrix}\)
   • Row P, column R: 33

Find a Hamiltonian cycle in the graph.

• Look for a cycle through every vertex: use vertices with only two edges first, since both edges must be used
• A-B-C-F-D-E-A
• It visits all 6 vertices once and returns to the start

Look at the graph. The graph has 8 vertices and 11 edges.

1. (a) Show that the graph is Hamiltonian.

   • Find a cycle through every vertex once: A-E-D-H-C-B-G-F-A
   • It has 8 vertices and returns to the start, so the graph is Hamiltonian

2. (b) Which edges are not used by your cycle?

   • The graph has 11 edges and the cycle uses 8
   • Edges not used: CD, DA, GH

A park warden checks seven huts, once each, along the paths shown in the graph. She does not have to return to where she began.

1. (a) Find a route that starts at D and visits every vertex exactly once.

   • D has degree 1, so start there.
   • Follow the edges: D–G–F–C–B–A–E.
   • Check: every vertex once, 6 edges.

2. (b) Explain why the graph has no Hamiltonian cycle.

   • Degree of D = 1.
   • A cycle must enter and leave D, which needs 2 edges.
   • So there is no Hamiltonian cycle.

The diagram shows the paths of a park. The vertices are junctions. A walker wants to use every path exactly once.

1. (a) Explain why it is possible to walk along every path once but not to finish where the walk began.

   • Degrees: A 2, B 4, C 3, D 4, E 3, F 4
   • Only C and E are odd, so the graph is semi-Eulerian
   • An Eulerian trail starts at one odd vertex and ends at the other, so the walk cannot end where it began

2. (b) Write down a route.

   • Start at C and finish at E
   • C-B-A-D-C-F-B-E-D-F-E

The graph shows roads between six towns. A delivery van must visit each town once and return to its depot at the start.

• The route must visit each of the six towns once and return, so it is a Hamiltonian cycle
• A-B-C-D-F-E-A
• Check: six different towns, back at the start

A graph has vertices A to E in this order and adjacency matrix \(A=\begin{pmatrix}0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0\end{pmatrix}\)

1. (a) Show that the graph is Hamiltonian.

   • Edges from the matrix: BC, CD, DA, AE, BE, CE, DE
   • A cycle through every vertex: A-D-C-B-E-A
   • It visits each vertex once and returns to the start

2. (b) Find the number of walks of length 5 from A to C.

   • From the calculator: \(A^5=\begin{pmatrix}24 & 27 & 33 & 38 & 45 \\ 27 & 24 & 38 & 33 & 45 \\ 33 & 38 & 44 & 52 & 58 \\ 38 & 33 & 52 & 44 & 58 \\ 45 & 45 & 58 & 58 & 64\end{pmatrix}\)
   • Row A, column C: 33

A connected graph has vertices with degrees 4, 4, 3, 3, 2, 2, 2.

1. (a) Explain why the graph has an Eulerian trail but no Eulerian circuit.

   • The odd degrees are 3 and 3: exactly two
   • Two odd vertices: an Eulerian trail exists (the graph is connected)
   • A circuit needs every degree even, so there is none

2. (b) Find the number of edges.

   • Each edge adds 1 to two degrees, so the degrees sum to twice the number of edges
   • 4 + 4 + 3 + 3 + 2 + 2 + 2 = 20
   • 20 ÷ 2 = 10 edges