Menu
Sign up Sign in

AI HL · AHL 1

Graph Theory

0 of 43 skills done

0
AHL 1.5

Eulerian and Hamiltonian graphs

AHL 1.5

Eulerian and Hamiltonian graphs

Target: I can find the degrees of a graph and say whether it is Eulerian, semi-Eulerian or neither. (+6 more)

By the end of this section

Key points

Eulerian graphs: every edge once

  • The degree of a vertex is the number of edges at it. A double edge counts twice.
  • An Eulerian circuit uses every edge once and returns to the start. It exists if and only if every vertex has even degree.
  • An Eulerian trail uses every edge once and finishes elsewhere. It exists if and only if exactly two vertices have odd degree. It starts at one and ends at the other.
  • Each time a walk passes through a vertex it uses two edges. That is why the odd vertices can only be the start and the end.

Explaining and showing

  • To explain why a graph is not Eulerian, name the odd vertices: more than 2 odd vertices means neither a circuit nor a trail.
  • To show a graph is semi-Eulerian, list the degrees, name the two odd vertices, then give the trail.
  • Check a trail by crossing off each edge as you use it. Pen on the page, no edge twice.

Hamiltonian graphs: every vertex once

  • A Hamiltonian cycle visits every vertex exactly once and returns to the start. A graph with one is Hamiltonian.
  • There is no degree test. To show a graph is Hamiltonian, give a cycle. A cycle through n vertices uses n edges, so some edges are not used.
  • A vertex of degree 2 must have both its edges in any Hamiltonian cycle. Start there.

From a matrix

  • Row sums of an adjacency matrix (no loops) are the degrees. Eulerian: every row sum even.
  • To draw a graph from a matrix, put a vertex for each row, in order, and join i to j wherever row i, column j is 1.
  • The entry of \(A^5\) in row i, column j counts walks of length 5 from i to j. Use the calculator.

Hamiltonian paths

  • A Hamiltonian path visits every vertex exactly once but does not have to return to the start. On n vertices it uses n − 1 edges.
  • A graph can have a Hamiltonian path and no Hamiltonian cycle.
  • A vertex of degree 1 can only be the start or the end of a Hamiltonian path. It also rules out a Hamiltonian cycle, because a cycle needs two edges at every vertex.

On the calculator

Powers of a matrix

  • Enter the adjacency matrix with the rows in the order the question gives.
  • Calculate \(A^5\) on the calculator and read the row of the start vertex and the column of the end vertex.

Screenshot and video to come

Explore: walk along a graph

Press a vertex to start. Then press a vertex joined to where you are, again and again, to build a walk. The sentence says what kind of walk it is.

Graph

Length
Edges used
Vertices visited
Odd vertices

Press a vertex to start a walk.

  1. On Six towns, find a walk that is a trail but not a path. Then find a path that is not a trail. Which one is impossible?
  2. Try to use every edge exactly once. Where do you have to start? Tick the box: what do the odd vertices tell you?
  3. On the Triangles graph, find an Eulerian circuit. Then try to visit every vertex exactly once and return to the start. Why does it fail?
  4. On Königsberg, try to cross every bridge once. How many odd vertices are there, and why does that stop you?

Explore: count walks with powers of A

Choose a graph, a start vertex, an end vertex and a length k. The matrix Ak counts the walks. When there are few, they are listed.

Graph
Start
End

Rows are where a walk starts. Columns are where it ends. The highlighted entry is the answer.

    Choose a start and an end vertex.

    1. Set k = 1. Which entries of A are 1? Check them against the edges in the drawing.
    2. Choose the same start and end vertex. Why can there be walks of length 2 from a vertex back to itself?
    3. On the loop graph, find an entry of A2 that is bigger than you expect. Which walks use the double edge?
    4. On One-way links, swap the start and the end. Why can the two answers be different?

    Worked examples

    Problems like the ones in class. Pick one, try it, then open the working.
    A semi-Eulerian graph

    Show that the graph is semi-Eulerian and find an Eulerian trail. How many edges does the trail use?

    ABCDEF
    Working
    1. Degrees

      A 2, B 4, C 3, D 2, E 4, F 3

      Count the edges at each vertex.

    2. Odd vertices

      Odd: C and F. All others even.

      Exactly two odd vertices: the graph is semi-Eulerian.

    3. Trail

      C-B-A-F-B-E-C-D-E-F

      Start at one odd vertex (C) and end at the other (F). Each edge is used once.

    4. Count

      9 edges

      A trail of 9 edges has 10 letters.

    Video walkthrough coming
    An Eulerian circuit

    Is the graph Eulerian, semi-Eulerian or neither? Find an Eulerian circuit if there is one. Give the sum of the degrees.

    ABECD
    Working
    1. Degrees

      A 2, B 2, E 4, C 2, D 2; sum = 12

      Every degree is even.

    2. Classify

      No odd vertices: Eulerian.

      An Eulerian circuit exists exactly when every vertex is even.

    3. Circuit

      A-B-E-C-D-E-A

      It starts and ends at the same vertex and uses each of the 6 edges once.

    Video walkthrough coming
    Why there is no circuit

    A town has four districts N, W, E and S joined by 7 bridges, as in the graph. Is it possible to cross every bridge exactly once? Explain.

    NWES
    Working
    1. Degrees

      N 3, W 5, E 3, S 3

      A double edge counts twice at each end.

    2. Odd vertices

      N, W, E, S: 4 odd vertices

      A trail can have only 2 odd vertices (its start and end). More than 2 means no trail.

    3. Conclude

      Not possible: the graph is neither Eulerian nor semi-Eulerian.

      Name the odd vertices in your answer.

    Video walkthrough coming
    Row sums of an adjacency matrix

    A graph has vertices A to E and adjacency matrix \(M=\begin{pmatrix}0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0\end{pmatrix}\). Is the graph Eulerian?

    Working
    1. Row sums

      A 2, B 3, C 4, D 3, E 2

      The sum of row i is the degree of vertex i (no loops here).

    2. Odd sums

      2 rows have an odd sum

      Odd rows are odd vertices.

    3. Conclude

      Not Eulerian (two odd vertices: semi-Eulerian)

      A graph is Eulerian only if every row sum is even.

    Video walkthrough coming
    Draw it, then count walks

    A graph has vertices P, Q, R and S in that order and adjacency matrix \(A=\begin{pmatrix}0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0\end{pmatrix}\). Draw the graph and find the number of walks of length 5 from P to Q.

    Working
    1. Edges from the 1s

      Row P: R, S. Row Q: R, S. Row R: P, Q, S.

      A 1 in row i, column j is an edge ij. The matrix is symmetric, so draw each edge once: PR, PS, QR, QS, RS.

    2. PQRS
      Draw

      Draw five edges: PR, PS, QR, QS, RS.

      Label the vertices in the order given.

    3. Power

      From the calculator: \(A^5=\begin{pmatrix}18 & 18 & 29 & 29 \\ 18 & 18 & 29 & 29 \\ 29 & 29 & 32 & 33 \\ 29 & 29 & 33 & 32\end{pmatrix}\)

      Walks of length 5.

    4. Read the entry

      Row P, column Q: 18

      There are 18 walks of length 5 from P to Q.

    Video walkthrough coming
    A Hamiltonian cycle

    Show that the graph is Hamiltonian. Which edges are not used? How many?

    ABCDEFGH
    Working
    1. Find a cycle

      A-B-C-D-H-G-F-E-A

      It visits each of the 8 vertices once and returns to the start. So the graph is Hamiltonian.

    2. Edges used

      AB, BC, CD, DH, HG, GF, FE, EA

      8 edges, one for each vertex.

    3. Edges left out

      DA, HE, BF, CG (4 edges)

      Compare the 12 edges of the graph with the 8 in the cycle.

    Video walkthrough coming
    A Hamiltonian path

    The graph shows the corridors between six rooms of a museum. A guard wants to walk through every room exactly once. She does not have to finish where she began. Show that this is possible, and say how many corridors she uses. Is there a Hamiltonian cycle?

    ABCFED
    Working
    1. Degrees

      A 1, B 4, C 2, D 2, E 3, F 2

      A has degree 1: a path can only start or end there.

    2. ABCFED
      Build a path

      A–B–C–D–E–F

      Start at A and move to a room you have not visited. Every room appears once.

    3. Count

      6 rooms, 5 corridors

      A Hamiltonian path on n vertices uses n − 1 edges. It is a Hamiltonian path, not a cycle: it does not return to A.

    4. A cycle?

      Degree of A = 1

      A cycle needs 2 edges at every vertex, and A has only one. There is no Hamiltonian cycle.

    Video walkthrough coming