Graphs and their vocabulary Problem set B

Graph M is shown.

1. (a) Is it simple?
2. (b) Is it connected?
3. (c) Is it complete?

Graph N is shown.

1. (a) Write down the degree of each vertex.
2. (b) Find the sum of the degrees and the number of edges. What do you notice?

Graph Y is shown.

1. (a) How many vertices and edges does it have?
2. (b) Is it a tree? Give a reason.

Think about the complete graph K9 on 9 vertices.

1. (a) Write down the degree of each vertex.
2. (b) Find the number of edges.

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?
2. (b) Is H connected?
3. (c) Is H a tree?

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.
2. (b) Is there a walk that crosses every bridge exactly once? If there is, write one down. If not, say why.

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?
2. (b) Which vertex has the greatest degree, and what is that degree?
3. (c) Find the sum of all the weights.

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

1. (a) Is the original network connected?
2. (b) The cable RU is cut, leaving a subgraph H. Is H connected?
3. (c) Is H a tree?

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

1. (a) How many edges does it have?
2. (b) Explain why it cannot be a simple graph.

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

1. (a) Show that \(n^2-n-132=0\).
2. (b) Use your calculator to find n.