Eulerian and Hamiltonian graphs Problem set B

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

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

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

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

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

Write down a Hamiltonian cycle for the graph.

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

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

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

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

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