Graph theory worksheet with answers

Free printable Graph theory worksheet: 6 problems from easy to exam level, with an answer key. Print it or save it as a PDF.

New worksheetPractise online with hints

For teachers: free to print, copy and use in class. Every new worksheet has new values and its own answer key. A link to ExamProblems on your course page is appreciated.

Name: ____________________   Date: ____________

1.Easy
ABCDEFG

Find the sum of the degrees of all vertices of the graph shown, Σ deg.

|V| = 7
Σ deg =
2.Easy
ABCDEF

Exactly one vertex of the graph has degree 3. Click it.

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
3.Medium

A tree has 4 vertices of degree 3, 3 vertices of degree 4, 4 vertices of degree 5, 4 vertices of degree 2, and all its other vertices are leaves (degree 1). How many leaves L does it have?

4 × deg 33 × deg 44 × deg 54 × deg 2
L =
4.Medium
ABCDEFGEuler circuitEuler path, no circuitneither

Does the connected graph have an Euler circuit, an Euler path that is not a circuit, or neither? Click your answer.

|V| = 7|E| = 8
  1. 1Euler circuit
  2. 2Euler path, no circuit
  3. 3neither
5.Hard
2184916111101914ABCDEFG

Prim’s algorithm builds a minimum spanning tree starting from vertex A. Click the edge it adds as edge number 6.

start: Ak = 6
  1. 1edge AB
  2. 2edge BC
  3. 3edge BD
  4. 4edge CE
  5. 5edge DF
  6. 6edge EF
  7. 7edge GB
  8. 8edge GC
  9. 9edge GD
  10. 10edge GE
6.Hard
10159112114ABCDEF

Use Dijkstra’s algorithm to find the length d(F) of the shortest path from A to F in the weighted graph.

start: Aend: F
d(F) =

Answer key

  1. 1. Σ deg = 14
  2. 2. D
  3. 3. L = 24
  4. 4. neither
  5. 5. edge EF
  6. 6. d(F) = 16

Full step-by-step solutions: practise this topic on examproblems.com.