Vertices, degrees, connectivity and Euler trails

A graph is a set of vertices joined by edges. The degree of a vertex counts the edges meeting there, and the degrees control whether you can trace the graph without lifting your pen.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What this topic covers

The handshaking lemma (handshaking lemma) says degrees sum to 2E. Whether you can traverse every edge once depends on Euler circuits and trails; trees have V − 1 edges. Specific results: bipartite graphs, Hall’s marriage theorem, max-flow min-cut and colouring theorems.

Each part of this topic has its own page with the formula, worked examples and a solver: Chromatic polynomial of a cycle, Max-flow min-cut theorem, Hall's marriage theorem, Brooks and four-colour theorems, Cayley's formula (labelled trees), Bipartite graphs, Dirac's theorem (Hamiltonian cycle).

Closely related topics: Sets and Venn diagrams, Logic and truth tables, Matrices, Modular arithmetic.

What is it used for?

A graph is a set of vertices joined by edges. Graph theory studies degrees, paths, cycles, trees and colouring.

How to solve it

  1. List the vertices and count the degree of each.
  2. Handshaking lemma: the degrees add up to twice the number of edges.
  3. A graph is connected if you can get from any vertex to any other.
  4. Euler circuit: connected and all degrees even.
  5. Euler trail: connected with exactly two odd vertices.

Worked examples

The examples marked with a button were worked out by the solver on this page. You can try each one yourself.

Example 1: graph with edges AB, BC, CD, DA, AC

Worked out by the solver on this page. Press the button to try it yourself.

Graph theory Answer checked
Answer
4 vertices, 5 edges; degrees A=3, B=2, C=3, D=2; connected\text{4 vertices, 5 edges; degrees A=3, B=2, C=3, D=2; connected}
  1. Vertices and edges
  2. Degree of each vertex (number of edges meeting there)
  3. Adjacency matrix
  4. Handshaking lemma
    The degrees always add up to twice the number of edges.
  5. Connected?
    Yes, every vertex can be reached from every other.
  6. Euler trails and circuits
    Euler trail exists (not a circuit): exactly two odd vertices, A and C, so start at one and end at the other.
  7. Check: the row sums of the adjacency matrix equal the degrees

Example 2: graph with edges AB, BC, CA, DE

Worked out by the solver on this page. Press the button to try it yourself.

Graph theory Answer checked
Answer
5 vertices, 4 edges; degrees A=2, B=2, C=2, D=1, E=1; not connected\text{5 vertices, 4 edges; degrees A=2, B=2, C=2, D=1, E=1; not connected}
  1. Vertices and edges
  2. Degree of each vertex (number of edges meeting there)
  3. Adjacency matrix
  4. Handshaking lemma
    The degrees always add up to twice the number of edges.
  5. Connected?
    No, the graph splits into separate parts.
  6. Euler trails and circuits
    No Euler trail: the graph is not connected.
  7. Check: the row sums of the adjacency matrix equal the degrees

Example 3: graph with edges AB, BC, CD, DA

Worked out by the solver on this page. Press the button to try it yourself.

Graph theory Answer checked
Answer
4 vertices, 4 edges; degrees A=2, B=2, C=2, D=2; connected\text{4 vertices, 4 edges; degrees A=2, B=2, C=2, D=2; connected}
  1. Vertices and edges
  2. Degree of each vertex (number of edges meeting there)
  3. Adjacency matrix
  4. Handshaking lemma
    The degrees always add up to twice the number of edges.
  5. Connected?
    Yes, every vertex can be reached from every other.
  6. Euler trails and circuits
    Euler circuit exists: the graph is connected and every vertex has even degree.
  7. Check: the row sums of the adjacency matrix equal the degrees

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Degree sum

Edges AB, BC, CD, DA, AC: degrees 3, 2, 3, 2 sum to 10

2 × 5 edges.

Edges

Degree sum 10: 5 edges

Sum ÷ 2.

Euler trail

Exactly 2 odd vertices: yes

A and C have degree 3.

Euler circuit

AB, BC, CD, DA: all degrees even

Circuit exists.

Word problems

Count degrees, use the handshaking lemma, and use the number of odd vertices to decide if an Euler trail or circuit exists.

Degrees

Degrees in the graph with AB, BC, CD, DA, AC.

  1. A3
  2. B2
  3. C3
  4. D2
  5. Check: sum 10 ✓10

Edges

Number of edges.

  1. Sum ÷ 25
  2. Check: ✓5

Euler trail Higher

Is there an Euler trail?

  1. Odd vertices2 (A and C)
  2. Check: yes, from A to C ✓2

Euler circuit Higher

AB, BC, CD, DA.

  1. Degreesall 2
  2. Check: 4 edges, all even ✓4

Common mistakes

Degree sum equals E

sum = 5 ✗

sum = 2E = 10 ✓

Each edge counted twice.

Euler circuit with odd vertices

two odd vertices ✗

needs all even ✓

Trail only.

Forgetting separate components

one component ✗

count components ✓

A graph can be disconnected.

Counting a loop once

one ✗

two ✓

A loop adds 2.

Exam tips

  1. Σdeg = 2E.
  2. All even: Euler circuit.
  3. Two odd: Euler trail.
  4. Tree: E = V − 1.
  5. Draw the graph.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Edges if the degree sum is 14 Foundation

7

2. Edges of K₅ Foundation

10

3. Edges of a tree on 9 vertices Foundation

8

4. Degree sum if E = 12 Higher

24

5. Odd vertices in a graph with degrees 3, 3, 2, 2 Higher

2

6. Edges of a 4-cycle Higher

4

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Vertex
A point.
Edge
A link.
Degree
Edges at a vertex.
Euler trail
Uses every edge once.
Tree
Connected with no cycles.
Bipartite
Two sets of vertices.

Frequently asked questions

What is the handshaking lemma?

The sum of the degrees is twice the number of edges.

When does an Euler circuit exist?

When the graph is connected and all vertices have even degree.

How many edges does a tree have?

V − 1.

Which page covers the lemma?

handshaking lemma.

Which page covers Euler trails?

Euler circuits and trails.

Which page covers trees?

edges in a tree.

More in Discrete maths and number theory and the formula sheets.