Graphs (Edexcel A Level Further Maths: Decision 1): Exam Questions

Draw the graph K₅

(i) In the context of graph theory explain what is meant by ‘semi-Eulerian’. 

(ii) Draw two semi-Eulerian subgraphs of K₅, each having five vertices but with a different number of edges. 

Explain why a graph with exactly five vertices with vertex orders 1, 2, 2, 3 and 4 cannot be a tree.

Figure 1

Define what is meant by a planar graph.

Starting at A, find a Hamiltonian cycle for the graph in Figure 1.

Arc AG is added to Figure 1 to create the graph shown in Figure 2.

Figure 2

Taking ABCDEFGA as the Hamiltonian cycle,

use the planarity algorithm to determine whether the graph shown in Figure 2 is planar. You must make your working clear and justify your answer.

Figure 1 shows the graph G

State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.

Write down an example of a Hamiltonian cycle on G.

State whether or not G is planar, justifying your answer.

State the number of arcs that would need to be added to G to make the graph K₅

Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages.

For the network represented in Figure 2, complete the initial time matrix in the table below.

The time matrix after four iterations of Floyd’s algorithm is shown in Table 1.

Perform the final iteration of Floyd’s algorithm that follows from Table 1, showing the time matrix for this iteration.

Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6

A tree, T, has exactly six nodes. The degrees of the six nodes of T are

where is an integer.

Explain how you know that T cannot be Eulerian.

(i) Determine the value of

(ii) Hence state whether T is semi-Eulerian or not. You must justify your answer.

Figure 2 shows a graph, G, with six nodes with degrees 1, 2, 3, 3, 3 and 4

Using the vertices in Diagram 1, draw a graph with exactly six nodes with degrees 1, 2, 3, 3, 3 and 4 that is not isomorphic to G.