Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/graph-theory/ahl-1-5/problems/

jmaths

IB Mathematics: Applications and Interpretation HL · AHL 1: Graph Theory · AHL 1.5

Eulerian and Hamiltonian graphs Problem set A Answers

Skills

  1. Odd vertices S and T. Trail S-R-P-T-Q-R-U-T

  2. Eulerian. Circuit A-B-C-D-A-E-H-C-G-B-F-A

  3. 4 odd vertices (B, C, D, F): more than 2, so neither

  4. M_1 and M_3 represent Eulerian graphs

    1. (a) Edges: PQ, QR, RS, SP, PR
    2. (b) 33

  6. A-B-C-F-D-E-A (one possible cycle)

    1. (a) A-E-D-H-C-B-G-F-A
    2. (b) CD, DA, GH
    1. (a) D–G–F–C–B–A–E (also D–G–F–E–A–B–C)
    2. (b) D has degree 1, and a cycle needs two edges at every vertex.

In context

    1. (a) Exactly two odd vertices (C and E): a trail exists, a circuit does not
    2. (b) C-B-A-D-C-F-B-E-D-F-E

  2. A-B-C-D-F-E-A (one possible route)

Stretch

    1. (a) A-D-C-B-E-A
    2. (b) 33
    1. (a) Exactly two odd degrees (3 and 3): semi-Eulerian, not Eulerian
    2. (b) 10 edges

jmaths.xyz · AI HL · AHL 1.5 Eulerian and Hamiltonian graphs