Eulerian and Hamiltonian graphs Problem set A

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

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

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

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}\)

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.
2. (b) Find the number of walks of length 5 from P to R.

Find a Hamiltonian cycle in the graph.

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

1. (a) Show that the graph is Hamiltonian.
2. (b) Which edges are not used by your cycle?

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.
2. (b) Explain why the graph has 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.
2. (b) Write down a route.

The graph shows roads between six towns. A delivery van must visit each town once and return to its depot 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.
2. (b) Find the number of walks of length 5 from A to C.

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.
2. (b) Find the number of edges.