AQA D1 2006 June — Question 7

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2006
SessionJune
TopicGraph Theory Fundamentals

7 A connected graph \(\mathbf { G }\) has \(m\) vertices and \(n\) edges.
    1. Write down the number of edges in a minimum spanning tree of \(\mathbf { G }\).
    2. Hence write down an inequality relating \(m\) and \(n\).
  1. The graph \(\mathbf { G }\) contains a Hamiltonian cycle. Write down the number of edges in this cycle.
  2. In the case where \(\mathbf { G }\) is Eulerian, draw a graph of \(\mathbf { G }\) for which \(m = 6\) and \(n = 12\).