Graphs and their vocabulary Problem set B Worked solutions

Graph M is shown.

1. (a) Is it simple?

   • No: there is a loop or a repeated edge

2. (b) Is it connected?

   • Yes: there is a route between every pair of vertices

3. (c) Is it complete?

   • No: a complete graph on 5 vertices has 10 edges, M has 7

Graph N is shown.

1. (a) Write down the degree of each vertex.

   • Count the edges at each vertex: P: 2, Q: 5, R: 2, S: 3, T: 3, U: 3

2. (b) Find the sum of the degrees and the number of edges. What do you notice?

   • 2 + 5 + 2 + 3 + 3 + 3 = 18
   • 9 edges
   • 18 = 2 × 9: each edge has two ends

Graph Y is shown.

1. (a) How many vertices and edges does it have?

   • Vertices: 7. Edges: 6

2. (b) Is it a tree? Give a reason.

   • A tree on 7 vertices has 6 edges and is connected with no cycle
   • It is not connected.
   • It contains a cycle.
   • So it is not a tree

Think about the complete graph K9 on 9 vertices.

1. (a) Write down the degree of each vertex.

   • Each vertex is joined to the other 8 vertices: degree 8

2. (b) Find the number of edges.

   • Sum of degrees: 9 × 8 = 72
   • Each edge is counted twice: 72 ÷ 2 = 36

Graph L is shown. Vertex Q and every edge at Q are deleted to give a subgraph H.

1. (a) How many vertices and edges does H have?

   • L has 6 vertices and 8 edges
   • Q has degree 3
   • H: 6 − 1 = 5 vertices, 8 − 3 = 5 edges

2. (b) Is H connected?

   • Connected: there is a route between every pair of vertices

3. (c) Is H a tree?

   • A tree on 5 vertices has 4 edges, H has 5
   • H is not a tree: it contains a cycle

A garden has a pond, with islands I and J, and two banks S and K. The graph shows the stepping bridges: each area of ground is a vertex and each bridge is an edge.

1. (a) Write down the degree of each vertex.

   • Count the bridges at each area: S: 3, K: 3, I: 3, J: 3

2. (b) Is there a walk that crosses every bridge exactly once? If there is, write one down. If not, say why.

   • Odd vertices: S, K, I and J
   • Only the start and end of a walk can have odd degree
   • Four odd vertices: no such walk

The graph shows bus routes between six stops. The number on each edge is the journey time in minutes.

1. (a) How many vertices and how many edges does the graph have?

   • Vertices: 6. Edges: 8

2. (b) Which vertex has the greatest degree, and what is that degree?

   • Degrees: P 2, Q 4, R 2, S 2, T 3, U 3
   • Q has the greatest degree: 4

3. (c) Find the sum of all the weights.

   • 12 + 9 + 14 + 10 + 8 + 15 + 11 + 16 = 95 minutes

Six sensors in a weather station are joined by cables, as shown.

1. (a) Is the original network connected?

   • There is a route between every pair of vertices

2. (b) The cable RU is cut, leaving a subgraph H. Is H connected?

   • No: {P, Q, R, S, T} and {U} are now separate

3. (c) Is H a tree?

   • H has 6 vertices and 5 edges. A tree has 5.
   • H is not a tree: it is not connected

A graph has 6 vertices with degrees 5, 5, 5, 1, 1, 1.

1. (a) How many edges does it have?

   • Sum of degrees = 5 + 5 + 5 + 1 + 1 + 1 = 18
   • Edges = 18 ÷ 2 = 9

2. (b) Explain why it cannot be a simple graph.

   • A vertex of degree 5 in a graph with 6 vertices is joined to every other vertex
   • Three such vertices are each joined to all three degree 1 vertices, so those would have degree at least 3, not 1

A complete graph has 66 edges. Let n be its number of vertices.

1. (a) Show that \(n^2-n-132=0\).

   • A complete graph has \(\frac{n(n-1)}{2}\) edges
   • \(\frac{n(n-1)}{2}=66\), so \(n^2-n=132\)
   • \(n^2-n-132=0\)

2. (b) Use your calculator to find n.

   • Polynomial solver, coefficients 1, −1, −132: n = −11 or n = 12
   • n is a number of vertices, so n = 12