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 2-regular graph has 8 vertices (every vertex has degree 2). How many edges |E| does it have?

n = 8k = 2
|E| =
2.Easy
AABBCCDD0111100010011010

The adjacency matrix of a simple undirected graph is shown. How many edges |E| does the graph have?

|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

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

3 × deg 43 × deg 2
L =
5.Hard
23131015414ABCDE

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

start: Ck = 2
  1. 1edge AB
  2. 2edge AC
  3. 3edge BC
  4. 4edge BD
  5. 5edge CE
  6. 6edge DE
  7. 7edge BE
6.Hard
58971131461211ABCDEFG

Dijkstra’s algorithm runs from A. Click the vertex that is settled (made permanent) in round 3; A itself is round 1.

start: Around 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G

Answer key

  1. 1. |E| = 8
  2. 2. |E| = 4
  3. 3. Euler circuit
  4. 4. L = 8
  5. 5. edge AB
  6. 6. C

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