Graphs and their vocabulary Problem set A

Graph G is shown.

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

Graph G 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 T 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 K7 on 7 vertices.

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

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

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

Six computers in a school lab are joined by cables, as shown.

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

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

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

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

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