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
ABCDE

Exactly one vertex of the graph has degree 3. Click it.

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
2.Easy

How many edges |E| does the complete bipartite graph K2,5 have?

K2,5
|E| =
3.Medium
ABCDEFGEuler 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| = 7|E| = 9
  1. 1Euler circuit
  2. 2Euler path, no circuit
  3. 3neither
4.Medium

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

|V| = 9|E| = 13
k =
5.Hard
581197417315ABCDEFG

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

start: Gk = 5
  1. 1edge AB
  2. 2edge BC
  3. 3edge BD
  4. 4edge CE
  5. 5edge DE
  6. 6edge DF
  7. 7edge EF
  8. 8edge GB
  9. 9edge GD
6.Hard
104117313171615ABCDEF

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

|V| = 6|E| = 9
W =

Answer key

  1. 1. B
  2. 2. |E| = 10
  3. 3. neither
  4. 4. k = 5
  5. 5. edge DE
  6. 6. W = 40

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