Graphs and their vocabulary Problem set A One question at a time

Graph G is shown.

1. (a) Is it simple?

   • Yes: no loops and no repeated edges

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, G has 6

Graph G is shown.

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

   • Count the edges at each vertex: A: 2, B: 4, C: 2, D: 3, E: 3, F: 2

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

   • 2 + 4 + 2 + 3 + 3 + 2 = 16
   • 8 edges
   • 16 = 2 × 8: each edge has two ends

Graph T is shown.

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

   • Vertices: 6. Edges: 6

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

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

Think about the complete graph K7 on 7 vertices.

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

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

2. (b) Find the number of edges.

   • Sum of degrees: 7 × 6 = 42
   • Each edge is counted twice: 42 ÷ 2 = 21

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

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

   • G has 6 vertices and 8 edges
   • D has degree 4
   • H: 6 − 1 = 5 vertices, 8 − 4 = 4 edges

2. (b) Is H connected?

   • Connected: the vertices split into separate pieces: {A, B, C} and {E, F}

3. (c) Is H a tree?

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

A park has two islands, P and Q, in a river. The banks are N and E. The graph shows the footbridges: each area of land is a vertex and each bridge is an edge.

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

   • Count the bridges at each area: N: 2, P: 3, Q: 4, E: 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: P and E. A walk can start at one and end at the other
   • One route: P–N–Q–P–E–Q–E
   • It uses all 6 bridges once

The graph shows cycle paths between six villages. The number on each edge is the length of the path in km.

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

   • Vertices: 6. Edges: 9

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

   • Degrees: A 2, B 5, C 2, D 3, E 3, F 3
   • B has the greatest degree: 5

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

   • 4 + 3 + 5 + 2 + 7 + 3 + 6 + 8 + 9 = 47 km

Six computers in a school lab 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 AB is cut, leaving a subgraph H. Is H connected?

   • H is connected: every vertex can still be reached

3. (c) Is H a tree?

   • H has 6 vertices and 5 edges. A tree has 5.
   • H is a tree: connected, no cycle

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

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

   • Sum of degrees = 4 + 4 + 4 + 1 + 1 = 14
   • Edges = 14 ÷ 2 = 7

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

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

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

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

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

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

   • Polynomial solver, coefficients 1, −1, −90: n = −9 or n = 10
   • n is a number of vertices, so n = 10