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 forest (a graph without cycles) has 39 vertices and 4 connected components. How many edges |E| does it have?

|V| = 39c = 4
|E| =
2.Easy
ABCDEFG

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

|V| = 7
Σ deg =
3.Medium

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

3 × deg 5
L =
4.Medium

A connected graph has 8 vertices and 13 edges. How many edges k must be removed to leave a spanning tree?

|V| = 8|E| = 13
k =
5.Hard
2211089563ABCDEFG

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) =
6.Hard
812101113131962018ABCDEFG

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

start: Dk = 2
  1. 1edge AB
  2. 2edge AC
  3. 3edge BC
  4. 4edge BD
  5. 5edge CE
  6. 6edge DE
  7. 7edge DF
  8. 8edge EF
  9. 9edge GB
  10. 10edge GC
  11. 11edge GE

Answer key

  1. 1. |E| = 35
  2. 2. Σ deg = 18
  3. 3. L = 11
  4. 4. k = 6
  5. 5. d(F) = 22
  6. 6. edge DF

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