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
AABBCCDD0111101011011010

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

|E| =
2.Easy
ABCDEF

Find the sum of the degrees of all vertices of the graph shown, Σ deg.

|V| = 6
Σ deg =
3.Medium

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

|V| = 6|E| = 10
k =
4.Medium
ABCDEEuler 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| = 5|E| = 6
  1. 1Euler circuit
  2. 2Euler path, no circuit
  3. 3neither
5.Hard
89105142311916ABCDEFG

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

k = 6
  1. 1edge AC
  2. 2edge BC
  3. 3edge BD
  4. 4edge CE
  5. 5edge DF
  6. 6edge EF
  7. 7edge GB
  8. 8edge GC
  9. 9edge GD
  10. 10edge GE
6.Hard
11261916144ABCDE

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

k = 2
  1. 1edge AB
  2. 2edge AC
  3. 3edge BC
  4. 4edge BD
  5. 5edge CE
  6. 6edge DE
  7. 7edge BE

Answer key

  1. 1. |E| = 5
  2. 2. Σ deg = 14
  3. 3. k = 5
  4. 4. Euler path, no circuit
  5. 5. edge BD
  6. 6. edge BE

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