This Question is designed to test your understanding of the core ideas of graph theory: namely paths,

circuits, degree and connectedness.

a) Graphs can be used to represent a variety of different situations. Describe a situation where it

would be appropriate to use a undirected multigraph. In this situation, what does each node

represent? What does each edge represent?

b) Describe a situation where it would be appropriate to use a simple directed graph. In this

situation, what does each node represent? What does each edge represent?

c) If possible, draw a graph with degree sequence (3, 1, 4, 2, 3). If this is not possible, explain why.

d) If possible, draw a graph containing a cycle which is simultaneously Hamiltonian AND Eulerian.

If this is not possible, explain why.

e) If possible, draw a connected graph containing a Eulerian circuit, but NO Hamiltonian path. If

this is not possible, explain why.

f) If possible, draw a disconnected graph containing a Eulerian circuit. If this is not possible,

explain why.