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 30 edges. How many vertices |V| does it have?

|E| = 30
|V| =
2.Easy

How many edges |E| does the complete bipartite graph K4,11 have?

K4,11
|E| =
3.Medium
ABCDEFEuler circuitEuler path, no circuitneither

Does the connected graph have an Euler circuit, an Euler path that is not a circuit, or neither? Click your answer.

|V| = 6|E| = 7
  1. 1Euler circuit
  2. 2Euler path, no circuit
  3. 3neither
4.Medium

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

K7
H =
5.Hard
612183151317219110ABCDEFG

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

k = 4
  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 GC
  10. 10edge GD
  11. 11edge GE
6.Hard
7101514112111ABCDEF

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) =

Answer key

  1. 1. |V| = 31
  2. 2. |E| = 44
  3. 3. Euler circuit
  4. 4. H = 360
  5. 5. edge GE
  6. 6. d(F) = 19

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