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 simple graph has 5 vertices with degrees 3, 2, 2, 2, 1. How many edges |E| does it have?

deg: 3, 2, 2, 2, 1
|E| =
2.Easy
AABBCCDDEE0110010001100010000101110

The adjacency matrix of a simple undirected graph is shown. Find the degree deg(A) of vertex A.

deg(A) =
3.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
4.Medium

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

2 × deg 44 × deg 5
L =
5.Hard
1012142013164617ABCDEFG

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 EF
  6. 6edge GB
  7. 7edge GC
  8. 8edge GD
  9. 9edge GE
6.Hard
ABCDE

How many walks of length 2 go from D to C? A walk may repeat vertices and edges. Call the number N.

M = adjacency matrixL = 2
N =

Answer key

  1. 1. |E| = 5
  2. 2. deg(A) = 2
  3. 3. neither
  4. 4. L = 18
  5. 5. edge EF
  6. 6. N = 2

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