Graph Theory Fundamentals

\includegraphics{figure_1} Use the planarity algorithm to show that the graph in Fig. 1 is planar. [4]

2. (a) Define the following terms

1. planar graph,
2. Hamiltonian cycle.
   (b) (i) Draw a graph of \(\mathrm { K } _ { 3,2 }\) in such a way as to show that it is planar.
3. Explain why the planarity algorithm cannot be used when drawing \(\mathrm { K } _ { 3,2 }\) as a planar graph.

1 This question is about the planar graph shown below. \includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-2_567_1317_395_374}

1. 1. Apply Kuratowski's theorem to verify that the graph is planar.
   2. Use Euler's formula to calculate the number of regions in a planar representation of the graph.
2. 1. Write down a Hamiltonian cycle for the graph.
   2. By finding a suitable pair of vertices, show that Ore's theorem cannot be used to prove that the graph, as shown above, is Hamiltonian.
3. 1. Draw the graph formed by using the contractions AB and CF .
   2. Use Ore's theorem to show that this contracted graph is Hamiltonian.

2. Explain what is meant, in a network, by (a) a walk, (b) a tour.
(2) (2) (Total 4 marks)

2. Explain what is meant, in a network, by (a) a walk, (b) a tour.
(2) (2) (Total 4 marks)

1 Which of the following graphs is not planar? Circle your answer.
[0pt] [1 mark] \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_186_301_1000_520} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_218_224_986_884} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_241_236_982_1201} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_241_241_982_1521}

1 The adjacency graph for a map has a vertex for each country. Two vertices are connected by an arc if the corresponding countries share a border.

1. Draw the adjacency graph for the following map of four countries. The graph is planar and you should draw it with no arcs crossing. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_531_1486_561_292}
2. Number the regions of your planar graph, including the outside region. Regarding the graph as a map, draw its adjacency graph.
3. Repeat parts (i) and (ii) for the following map. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_533_1484_1361_294}

Each of the following symbols consists of boundaries enclosing regions. \includegraphics{figure_1} The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for \includegraphics{figure_2} is \(\bullet \longrightarrow \bullet \longrightarrow \bullet\).

1. Produce the graph for the symbol \includegraphics{figure_3}. [1]
2. Give two symbols each having the graph \(\bullet \longrightarrow \bullet\). [2]
3. Produce the graph for the symbol \includegraphics{figure_4}. [2]
4. Produce a single graph for the composite symbol \includegraphics{figure_5}. [2]
5. Give the name of a connected graph with \(n\) nodes and \(n - 1\) arcs. [1]

3 The adjacency graph of a cube \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_106_108_214_735}
is shown. Vertices on the graph represent faces of the cube. Two vertices are connected by an arc if the corresponding faces of the cube share an edge. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_401_464_246_1334} The second graph is the complement of the adjacency graph, i.e. the graph that consists of the same vertices together with the arcs that are not in the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_403_464_737_1334} Throughout this question we wish to colour solids so that two faces that share an edge have different colours. The second graph shows that the minimum number of colours required for a cube is three, one colour for the top and base, one for the front and back, and one for the left and right.

1. Draw the adjacency graph for a square-based pyramid, and draw its complement. Hence find the minimum number of colours needed to colour a square-based pyramid. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_161_202_1434_1548}
2. (A) Draw the adjacency graph for an octahedron, and draw its complement.
   (B) An octahedron can be coloured using just two colours. Explain how this relates to the complement of the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_227_205_1731_1548}

7

1. A simple connected graph has 4 edges and \(m\) vertices. State the possible values of \(m\).
2. A simple connected graph has \(n\) edges and 4 vertices. State the possible values of \(n\).
3. A simple connected graph, \(G\), has 5 vertices and is Eulerian but not Hamiltonian. Draw a possible graph \(G\).
   [0pt] [2 marks]

1. Draw the graph \(K_5\) [1]
2. 1. In the context of graph theory explain what is meant by 'semi-Eulerian'.
   2. Draw two semi-Eulerian subgraphs of \(K_5\), each having five vertices but with a different number of edges. [3]
3. Explain why a graph with exactly five vertices with vertex orders 1, 2, 2, 3 and 4 cannot be a tree. [2]

2 A simple graph is one which has no repeated arcs and no arc that joins a vertex to itself.

1. Draw a simple graph that connects four vertices using five arcs.
2. Explain why, in any graph, there must be an even number of odd vertices.
3. By considering the orders of the vertices, show that there is only one possible simple graph that connects four vertices using five arcs.

2

1. Draw three mathematically different graphs, labelled graph \(A\), graph \(B\) and graph \(C\), each with four vertices, of orders 1, 3, 3 and 3, and five arcs.
2. Explain how you know that none of the graphs from part (i) is Eulerian.

1 Alfred, Ben, Charles and David meet, and some handshaking takes place.

• Alfred shakes hands with David.
• Ben shakes hands with Charles and David.
• Charles shakes hands with Ben and David.
  1. Complete the bipartite graph in your answer book showing A (Alfred), B (Ben), C (Charles) and D (David), and the number of people each shakes hands with.
  2. Explain why, whatever handshaking takes place, the resulting bipartite graph cannot contain both an arc terminating at 0 and another arc terminating at 3 .
  3. Explain why, whatever number of people meet, and whatever handshaking takes place, there must always be two people who shake hands with the same number of people.

2

1. Draw a graph with five vertices of orders 1, 2, 2, 3 and 4 .
2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is.
3. Explain why a graph with five vertices of orders \(1,2,2,3\) and 4 cannot be a tree.

5 The planar graph \(P\) is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-08_410_406_360_817} 5

1. Determine the number of faces of \(P\).
   5
2. Akwasi claims that \(P\) is semi-Eulerian as it is connected and it has exactly two vertices with even degree. Comment on the validity of Akwasi's claim. \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-09_2488_1716_219_153}

Graph \(A\) is a connected planar graph with 12 vertices, 18 edges and \(n\) faces. Find the value of \(n\) Circle your answer. [1 mark] 4 8 28 32

1 The graph shows routes that are available to an international lorry driver. The solid arcs represent motorways and the broken arcs represent ferry crossings. \includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-2_668_1131_587_466}

1. Give a route from Milan to Chania involving exactly two ferry crossings. How many such routes are there?
2. Give a route from Milan to Chania involving exactly three ferry crossings. How many such routes are there?
3. Give a route from Milan to Chania using as many ferry crossings as possible, without repeating any arc.
   [0pt]
4. Give a route leaving Piraeus and finishing elsewhere which uses every arc once and only once.[3]

3 Consider the following algorithm.
Step 1: Input a positive integer \(n\).
Step 2 : Draw a graph consisting of \(n\) vertices and no arcs.
Step 3 : Create a new vertex and join it directly to every vertex of order 0.
Step 4: Create a new vertex and join it directly to every vertex of odd order.
Step 5 : Stop.

1. Draw separate diagrams to show the result of applying this algorithm in the following cases.
   1. \(n = 1\)
   2. \(n = 2\)
   3. \(n = 3\)
   4. \(n = 4\)
   5. State how many arcs are in the graph that results when the algorithm is applied to a set of \(n\) vertices.

1. Draw the complete graph \(K_5\). [1 mark]
2. Demonstrate that no planar drawing is possible for \(K_5\). [2 marks]
3. Draw the complete graph \(K_{3,3}\). [1 mark]
4. Demonstrate that no planar drawing is possible for \(K_{3,3}\). [2 marks]

An adjacency matrix for the simple graph \(G\) is shown below. \includegraphics{figure_5}

1. Using the adjacency matrix, explain why \(G\) is not a complete graph. [2 marks]
2. State, with a reason, whether \(G\) is Eulerian, semi-Eulerian or neither. [2 marks]
3. Draw a graph that is the complement of \(G\) [3 marks]

Find an expression for the number of edges in the complete bipartite graph, \(K_{m,n}\) Circle your answer. [1 mark] \(\frac{m}{n}\) \quad\quad \(m - n\) \quad\quad \(m + n\) \quad\quad \(mn\)

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]

Explain what is meant by a planar graph. (Total 2 marks)

1 A graph has 5 vertices and 6 edges.
Find the sum of the degrees of the vertices. Circle your answer. 10111215

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

4 The connected planar graph \(P\) has the adjacency matrix 4

1. Draw \(P\) 4
2. Using Euler's formula for connected planar graphs, show that \(P\) has exactly 5 faces. 4
3. Ore's theorem states that a simple graph with \(n\) vertices is Hamiltonian if, for every pair of vertices \(X\) and \(Y\) which are not adjacent, $$\text { degree of } X + \text { degree of } Y \geq n$$ where \(n \geq 3\) Using Ore's theorem, prove that the graph \(P\) is Hamiltonian.
   Fully justify your answer.

8

1. The diagram shows a graph \(\mathbf { G }\) with 9 vertices and 9 edges. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_188_204_411_708} \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_184_204_415_1105} \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_183_204_612_909}
   1. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make a connected graph. Draw an example of such a graph.
   2. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Hamiltonian. Draw an example of such a graph.
   3. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Eulerian. Draw an example of such a graph.
2. A complete graph has \(n\) vertices and is Eulerian.
   1. State the condition that \(n\) must satisfy.
   2. In addition, the number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of \(n\).

5 There are three non-isomorphic trees on five vertices.

1. Draw an example of each of these trees.
2. State three properties that must be satisfied by the vertex orders of a tree on six vertices.
3. List the five different sets of possible vertex orders for trees on six vertices.
4. Draw an example of each type listed in part (iii).

3 Fig. 3 shows a graph representing the seven bus journeys run each day between four rural towns. Each directed arc represents a single bus journey. \begin{figure}[h] \end{figure}

1. Show that if there is only one bus, which is in service at all times, then it must start at one town and end at a different town. Give the start town and the end town.
2. Show that there is only one Hamilton cycle in the graph. Show that, if an extra journey is added from your end town to your start town, then there is still only one Hamilton cycle.
3. A tourist is staying in town B. Give a route for her to visit every town by bus, visiting each town only once and returning to B . Section B (48 marks)