7.02d Complete graphs: K_n and number of arcs

6 The complete graph \(K _ { n } ( n > 1 )\) has every one of its \(n\) vertices connected to each of the other vertices by a single edge.

1. Draw the complete graph \(K _ { 4 }\).
2. 1. Find the total number of edges for the graph \(K _ { 8 }\).
   2. Give a reason why \(K _ { 8 }\) is not Eulerian.
3. For the graph \(K _ { n }\), state in terms of \(n\) :
   1. the total number of edges;
   2. the number of edges in a minimum spanning tree;
   3. the condition for \(K _ { n }\) to be Eulerian;
   4. the condition for the number of edges of a Hamiltonian cycle to be equal to the number of edges of an Eulerian cycle.

2 A small party is held in a country house. There are 10 men and 10 women, and there are 10 dances. For each dance a number of pairings, each of one man and one woman, are formed. The same pairing can appear in more than one dance. A graph is to be drawn showing who danced with whom during the evening, ignoring repetitions.

1. Name the type of graph which is appropriate.
2. What is the maximum possible number of arcs in the graph? Dashing Mr Darcy dances with every woman except Elizabeth, who will have nothing to do with him. She dances with eight different men. Prince Charming only dances with Cinderella. Cinderella only dances with Prince Charming and with Mr Darcy. The three ugly sisters only have one dance each.
3. Add arcs to the graph in your answer book to show this information.
4. What is the maximum possible number of arcs in the graph?

4. \begin{figure}[h] \end{figure} Figure 3 shows the graph \(K _ { 4 }\).

1. State the features of the graph that identify it as \(K _ { 4 }\).
2. In \(K _ { 4 }\), the Hamiltonian cycles \(A B C D A , B C D A B , C D A B C\) and \(D A B C D\) are usually regarded as being the same cycle. Find the number of distinct Hamiltonian cycles in
   1. \(\quad K _ { 4 }\),
   2. \(K _ { 5 }\),
   3. \(K _ { 10 }\).
3. In a weighted network, 8 possible routes must be placed in ascending order according to their lengths. The routes have the following lengths in kilometres: $$\begin{array} { l l l l l l l l } 27 & 25 & 29 & 32 & 19 & 24 & 17 & 26 \end{array}$$ Use a quick sort to obtain the sorted list, giving the state of the list after each comparison and indicating the pivot elements used.

1. (a) Make plane drawings of each of the graphs shown in Figure 1.

Graph 1 \begin{figure}[h] \end{figure} (b) State the name given to Graph 1 and write down the features that identify it.
(c) State, with a reason, whether it is possible to add further arcs to Graph 2 such that it remains a simple connected graph. No further vertices may be added.
(1 mark)

4 The complete bipartite graph \(K _ { 3,4 }\) connects the vertices \(\{ 2,4,6 \}\) to the vertices \(\{ 1,3,5,7 \}\).

1. How many arcs does the graph \(K _ { 3,4 }\) have?
2. Deduce how many different paths are there that pass through each of the vertices once and once only. The direction of travel of the path does not matter. The arcs are weighted with the product of the numbers at the vertices that they join.
3. (a) Use an appropriate algorithm to find a minimum spanning tree for this network.
   (b) Give the weight of the minimum spanning tree.

2 Two graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. List the vertex degrees for each graph.
2. Prove that the graphs are non-isomorphic. The two graphs are joined together by adding an arc connecting J and T .
3. 1. Explain how you know that the resulting graph is not Eulerian.
   2. Describe how the graph can be made Eulerian by adding one more arc. The vertices of the graph \(K _ { 3 }\) are connected to the vertices of the graph \(K _ { 4 }\) to form the graph \(K _ { 7 }\).
4. Explain why 12 arcs are needed connecting \(K _ { 3 }\) to \(K _ { 4 }\).

4 Graph G is a simply connected Eulerian graph with 4 vertices.

1. 1. Explain why graph G cannot be a complete graph.
   2. Determine the number of arcs in graph G, explaining your reasoning.
   3. Show that graph G is a bipartite graph. Graph H is a digraph with 4 vertices and no undirected arcs. The adjacency matrix below shows the number of arcs that directly connect each pair of vertices in digraph H . From \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{To}

      	A	B	C	D
      A	0	1	0	1
      B	0	0	2	0
      C	2	1	0	1
      D	0	1	1	0

      \end{table}
2. 1. Write down a feature of the adjacency matrix that shows that H has no loops.
   2. Find the number of \(\operatorname { arcs }\) in H .
   3. Draw a possible digraph H .
   4. Show that digraph H is semi-Eulerian by writing down a suitable trail.

1 The famous fictional detective Agatha Parrot is investigating a murder. She has identified six suspects: Mrs Lemon \(( L )\), Prof Mulberry \(( M )\), Mr Nutmeg \(( N )\), Miss Olive \(( O )\), Capt Peach \(( P )\) and Rev Quince \(( Q )\). The table shows the weapons that could have been used by each suspect.

1. Draw a bipartite graph to represent this information. Put the weapons on the left-hand side and the suspects on the right-hand side. Agatha Parrot is convinced that all six suspects were involved, and that each used a different weapon. She originally thinks that the axe handle was used by Prof Mulberry, the broomstick by Miss Olive, the drainpipe by Mrs Lemon, the fence post by Mr Nutmeg and the golf club by Capt Peach. However, this would leave the hammer for Rev Quince, which is not a possible pairing.
2. Draw a second bipartite graph to show this incomplete matching.
3. Construct the shortest possible alternating path from \(H\) to \(Q\) and hence find a complete matching. Write down which suspect used each weapon.
4. Find a different complete matching in which none of the suspects used the same weapon as in the matching from part (iii).

1 The connected graph \(G\) is shown below. \includegraphics[max width=\textwidth, alt={}, center]{ecbeedf5-148e-40ad-b8a2-a7aa3db4a115-02_542_834_630_603} The graphs \(A\) and \(B\) are subgraphs of \(G\) Both \(A\) and \(B\) have four vertices. 1

1. The graph \(A\) is a tree with \(x\) edges.
   State the value of \(x\) Circle your answer. 3459 1
2. The graph \(B\) is simple-connected with \(y\) edges.
   Find the maximum possible value of \(y\) Circle your answer. 3459

A simple connected graph has six vertices.

1. One vertex has degree \(x\). State the greatest and least possible values of \(x\). [2 marks]
2. The six vertices have degrees $$x - 2, \quad x - 2, \quad x, \quad 2x - 4, \quad 2x - 4, \quad 4x - 12$$ Find the value of \(x\), justifying your answer. [2 marks]

1. Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3. [1]

A simple graph is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. 1. Draw a graph with five vertices of orders 1, 1, 2, 2 and 4 that is neither simple nor connected. [2]
   2. Explain why your graph from part (a) is not semi-Eulerian. [1]
   3. Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. [1]

Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.

1. 1. Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour. [2]
   2. Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour. [2]