Eulerian and Hamiltonian graphs Problem set B Answers

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

Eulerian. Circuit A-D-C-F-B-E-D-F-E-A

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

N_1 represents an Eulerian graph

1. (a) Edges: PQ, QR, RS, QS
2. (b) 6

A-D-E-H-C-G-B-F-A (one possible cycle)

1. (a) P-Q-R-S-U-T-P
2. (b) ST, PS, RU, QU

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

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

P-Q-R-U-T-S-P (one possible route)

1. (a) A-B-C-D-E-A
2. (b) 22

1. (a) Exactly two odd degrees (3 and 3): semi-Eulerian, not Eulerian
2. (b) 11 edges