Year 12 Graph Theory Summative Assessment

Which of the following statements is false?

• The sum of degrees of the vertices is equal to twice the number of edges in any graph

• A loop contributes two degrees to a vertex because a loop is attached to its vertex at both ends.

• A subgraph cannot contain any isolated vertices

• A simple graph does not contain any loops or duplicate or multiple edges

• A complete graph contains edges between every pair of vertices

Is it possible to trace out a continuous walk that crosses each of the Königsberg bridges only once?

• No because graph has only one two even vertices

• 1. Yes because the graph has only two odd vertices

• No because the graph has only odd vertices

• Yes because the graph has only even vertices

• None of the above

What is the degree of vertex E?

• 1

• 2

• 3

• 4

• 5

An Euler Circuit:

• passes through each vertex once only and starts and finishes at the same vertex.

• passes along each edge once only and starts and finishes at the same vertex.

• passes through each vertex once only and starts and finishes at different vertices.

• 1. passes along each edge once only and starts and finishes at different vertices.

• starts and finishes at different vertices.

The length of the shortest path from F to B in the network shown is

• 15

• 16

• 17

• 18

• 19

For which one of the following graphs is the sum of the degrees of the vertices equal to 16?

• 
• 
• 
• 
• 

A Hamilton circuit:

• passes through each vertex once only and starts and finishes at the same vertex.

• passes along each edge once only and starts and finishes at the same vertex.

• passes through each vertex once only and starts and finishes at different vertices.

• passes along each edge once only and starts and finishes at different vertices.

• starts and finishes at different vertices.

For the graph below:

• v=5,e=7,f=2

• v=5,e=7,f=3

• 
  v=5,e=7,f=4

• v=6,e=6,f=2

• v=6,e=6,f=3

For a connected graph to have an Euler path but not an Euler circuit:

• all vertices must be odd

• all vertices must be even

• there must be exactly two odd vertices and the rest even

• there must be exactly two even vertices and the rest odd

• an odd vertex must be followed by an even vertex

The diagram below shows pathways through a forest. The distance between each checkpoint (in metres) is shown on the diagram. A group of trekkers want to get from checkpoint A to checkpoint D by travelling the least distance. Find the route that has the shortest distance.

• A−B−D

• A−B−E−D

• A−C−B−D

• A−C−D

• A−C−B−E−D