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

How many edges |E| does the complete graph K7 have?

K7
|E| =
2.Easy

How many edges |E| does the complete bipartite graph K5,12 have?

K5,12
|E| =
3.Medium

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

4 × deg 43 × deg 5
L =
4.Medium

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

|V| = 15|E| = 20
k =
5.Hard
1581671252420ABCDEFG

Kruskal’s algorithm builds a minimum spanning tree. Click the edge it adds as edge number 3; skipped edges do not count.

k = 3
  1. 1edge AB
  2. 2edge AC
  3. 3edge BC
  4. 4edge BD
  5. 5edge CE
  6. 6edge DE
  7. 7edge DF
  8. 8edge GB
  9. 9edge GD
6.Hard
2691713117ABCDE

Find the total weight W of a minimum spanning tree of the weighted graph.

|V| = 5|E| = 7
W =

Answer key

  1. 1. |E| = 21
  2. 2. |E| = 60
  3. 3. L = 19
  4. 4. k = 6
  5. 5. edge DE
  6. 6. W = 26

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