AQA D1 2005 June — Question 4

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

4
  1. In the complete graph \(\mathrm { K } _ { 7 }\), every one of the 7 vertices is connected to each of the other 6 vertices by a single edge. Find or write down:
    1. the number of edges in the graph;
    2. the number of edges in a minimum spanning tree;
    3. the number of edges in a Hamiltonian cycle.
    1. Explain why the graph \(\mathrm { K } _ { 7 }\) is Eulerian.
    2. Write down the condition for \(\mathrm { K } _ { n }\) to be Eulerian.
  2. A connected graph has 6 vertices and 10 edges. Draw an example of such a graph which is Eulerian.