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

A simple graph has 5 vertices with degrees 4, 3, 3, 2, 2. How many edges |E| does it have?

deg: 4, 3, 3, 2, 2
|E| =
2.Easy

A tree has 6 edges. How many vertices |V| does it have?

|E| = 6
|V| =
3.Medium

How many different Hamilton circuits H does the complete graph K6 have? Circuits that differ only in the starting vertex or the direction count as the same.

K6
H =
4.Medium

A tree has 3 vertices of degree 3, 2 vertices of degree 4, 3 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?

3 × deg 32 × deg 43 × deg 54 × deg 2
L =
5.Hard
10561211418ABCDE

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

start: Ek = 3
  1. 1edge AB
  2. 2edge AC
  3. 3edge BC
  4. 4edge BD
  5. 5edge CE
  6. 6edge DE
  7. 7edge BE
6.Hard
91212151196112ABCDEFG

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

start: Aend: E
d(E) =

Answer key

  1. 1. |E| = 7
  2. 2. |V| = 7
  3. 3. H = 60
  4. 4. L = 18
  5. 5. edge AC
  6. 6. d(E) = 27

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