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

How many edges |E| does the complete graph K8 have?

K8
|E| =
2.Easy

A simple graph has 7 vertices with degrees 3, 3, 3, 3, 2, 1, 1. How many edges |E| does it have?

deg: 3, 3, 3, 3, 2, 1, 1
|E| =
3.Medium

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

K5
H =
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| = 5
  1. 1Euler circuit
  2. 2Euler path, no circuit
  3. 3neither
5.Hard
ABCDE

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

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

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 BC
  3. 3edge BD
  4. 4edge CE
  5. 5edge DE
  6. 6edge DF
  7. 7edge EF
  8. 8edge GC
  9. 9edge GD
  10. 10edge GE

Answer key

  1. 1. |E| = 28
  2. 2. |E| = 8
  3. 3. H = 12
  4. 4. neither
  5. 5. N = 3
  6. 6. edge GD

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