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 tree has 20 vertices. How many edges |E| does it have?

|V| = 20
|E| =
2.Easy

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

deg: 3, 3, 3, 2, 2, 1
|E| =
3.Medium

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

3 × deg 33 × deg 5
L =
4.Medium

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

4 × deg 33 × deg 42 × deg 5
L =
5.Hard
7914161031517620ABCDEFG

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

start: Fk = 6
  1. 1edge AC
  2. 2edge BC
  3. 3edge BD
  4. 4edge CE
  5. 5edge DE
  6. 6edge DF
  7. 7edge EF
  8. 8edge GB
  9. 9edge GC
  10. 10edge GD
6.Hard
1635281461419911ABCDEFG

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

|V| = 7|E| = 12
W =

Answer key

  1. 1. |E| = 19
  2. 2. |E| = 7
  3. 3. L = 14
  4. 4. L = 18
  5. 5. edge AC
  6. 6. W = 24

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