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

Explain why the graph is semi-Eulerian, then find an Eulerian trail.

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

Decide whether the graph is Eulerian. If it is, write down an Eulerian circuit.

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

Show that the graph has neither an Eulerian circuit nor an Eulerian trail.

• Degrees: A 4, B 3, C 1, D 3, E 2, F 3, G 4, H 2
• 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

Decide which of these adjacency matrices are Eulerian graphs. \(N_1=\begin{pmatrix}0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0\end{pmatrix}\), \(N_2=\begin{pmatrix}0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0\end{pmatrix}\), \(N_3=\begin{pmatrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\)

• N_1: row sums 2, 2, 2, 4, 4, 4 (all even)
• N_2: row sums 3, 3, 3, 3, 4, 2 (some odd)
• N_3: row sums 3, 2, 3, 2 (some odd)
• Eulerian when every row sum is even: N_1

The vertices P, Q, R and S of a graph are listed in that order, and its adjacency matrix is \(A=\begin{pmatrix}0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 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, QS
   • 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 S.

   • From the calculator: \(A^5=\begin{pmatrix}2 & 11 & 6 & 6 \\ 11 & 14 & 17 & 17 \\ 6 & 17 & 12 & 13 \\ 6 & 17 & 13 & 12\end{pmatrix}\)
   • Row P, column S: 6

Write down a Hamiltonian cycle for the graph.

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

Here is a graph. The graph has 6 vertices and 10 edges.

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

   • Find a cycle through every vertex once: P-Q-R-S-U-T-P
   • It has 6 vertices and returns to the start, so the graph is Hamiltonian

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

   • The graph has 10 edges and the cycle uses 6
   • Edges not used: ST, PS, RU, QU

A courier delivers to seven offices, once each, along the corridors shown in the graph. He does not have to return to where he began.

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

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

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

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

The diagram shows the corridors of a museum. The vertices are rooms. A cleaner wants to pass along every corridor exactly once.

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

   • Degrees: A 3, B 2, C 2, D 2, E 3, F 2, G 2, H 4
   • Only A 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 A and finish at E
   • A-B-F-A-E-D-H-C-G-H-E

The graph shows direct flights between six airports. A tour company wants a trip that lands at each airport once and ends at the starting airport.

• The route must visit each of the six airports once and return, so it is a Hamiltonian cycle
• P-Q-R-U-T-S-P
• Check: six different airports, back at the start

The vertices A to E of a graph are in order, and its adjacency matrix is \(A=\begin{pmatrix}0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0\end{pmatrix}\)

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

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

2. (b) Find the number of walks of length 5 from B to D.

   • From the calculator: \(A^5=\begin{pmatrix}26 & 40 & 26 & 51 & 51 \\ 40 & 8 & 40 & 22 & 22 \\ 26 & 40 & 26 & 51 & 51 \\ 51 & 22 & 51 & 40 & 41 \\ 51 & 22 & 51 & 41 & 40\end{pmatrix}\)
   • Row B, column D: 22

A connected graph has these vertex degrees: 4, 3, 3, 2, 2, 2, 2, 4.

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 + 3 + 3 + 2 + 2 + 2 + 2 + 4 = 22
   • 22 ÷ 2 = 11 edges