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
AABBCCDDEE0010000101110010000101110

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

|E| =
2.Easy
ABCDEF

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

deg = 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
3.Medium

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

|V| = 13|E| = 17
k =
4.Medium

A tree has 2 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?

2 × deg 33 × deg 42 × deg 5
L =
5.Hard
ABCDE

How many closed walks of length 2 start and end at B? A walk may repeat vertices and edges. Call the number N.

M = adjacency matrixL = 2
N =
6.Hard
131188167311414ABCDEFG

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

k = 5
  1. 1edge AB
  2. 2edge AC
  3. 3edge BC
  4. 4edge CE
  5. 5edge DE
  6. 6edge DF
  7. 7edge EF
  8. 8edge GB
  9. 9edge GC
  10. 10edge GE

Answer key

  1. 1. |E| = 5
  2. 2. B
  3. 3. k = 5
  4. 4. L = 16
  5. 5. N = 3
  6. 6. edge CE

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