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 7 vertices with degrees 4, 4, 3, 3, 2, 1, 1. How many edges |E| does it have?

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

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

|E| = 12
|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 connected graph has 15 vertices and 21 edges. How many edges k must be removed to leave a spanning tree?

|V| = 15|E| = 21
k =
5.Hard
415985339144ABCDEFG

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
3217201645151918ABCDEFG

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 BD
  4. 4edge DE
  5. 5edge DF
  6. 6edge EF
  7. 7edge GB
  8. 8edge GC
  9. 9edge GD
  10. 10edge GE

Answer key

  1. 1. |E| = 9
  2. 2. |V| = 13
  3. 3. H = 60
  4. 4. k = 7
  5. 5. d(F) = 15
  6. 6. edge EF

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