myLearning

Step 21 · Proofs and discrete maths topics

Describe networks as graphs of vertices and edges, use degrees to count edges, decide when a graph has an Euler circuit, and work with trees.

Vertices, edges and degrees

A graph is a set of vertices joined by edges. The degree of a vertex is the number of edges that meet it. Every edge has two ends, so adding all the degrees counts every edge twice: the handshake lemma.

∑deg⁡(v)=2×(number of edges)\sum \deg(v) = 2 \times (\text{number of edges})

Example: Counting edges

A graph has 6 vertices, each of degree 3. How many edges does it have?

  1. The degrees add to 18.
  2. 18 ÷ 2 = 9.

Answer9

Example: An impossible graph

Can a graph have degrees 3, 3, 3, 2, 2?

  1. The degrees add to 13, which is odd.

AnswerNo: the degrees must add to an even number

Paths and Euler circuits

A path walks along edges from vertex to vertex. A graph is connected if every two vertices are joined by a path. An Euler circuit uses every edge exactly once and returns to where it started.

A connected graph withResult
Every degree evenAn Euler circuit
Exactly two odd degreesAn Euler path from one odd vertex to the other
More than two odd degreesNeither
A square with one diagonal. A and C have degree 3, and B and D have degree 2, so a path can use every edge once, from A to C.

Example: A drawing puzzle

Can a square with both diagonals be drawn without lifting the pen or going over a line twice?

  1. Each corner has degree 3, so there are four odd vertices.

AnswerNo

Example: Königsberg's bridges

Seven bridges joined four land masses, with degrees 5, 3, 3 and 3. Could a walk cross each bridge exactly once?

  1. All four vertices have odd degree.

AnswerNo, as Euler showed in 1736

Trees

A tree is a connected graph with no cycles. Trees are the leanest connected graphs: remove any edge and the graph falls apart; add any edge and a cycle appears.

Example: Counting edges

How many edges does a tree with 10 vertices have?

  1. Every tree with n vertices has n − 1 edges.

Answer9

Example: Leaves

Why does every tree with at least 2 vertices have a leaf, a vertex of degree 1?

  1. Follow a longest path in the tree.
  2. Its last vertex cannot have another neighbor: that would make a longer path or a cycle.

AnswerSo the end of a longest path is a leaf

Try it yourself

Work each one on paper first, then open the answer to check.

  1. A graph has degrees 4, 3, 3, 2, 2. How many edges does it have?

    Show answer

    7

  2. Can a graph have exactly one vertex of odd degree?

    Show answer

    No

  3. Does a connected graph with degrees 2, 2, 4, 2 have an Euler circuit?

    Show answer

    Yes: every degree is even

  4. How many edges does a tree with 25 vertices have?

    Show answer

    24

  5. A connected graph has 8 vertices and 7 edges. Is it a tree?

    Show answer

    Yes

  6. What is the degree of each vertex in a cycle of 5 vertices?

    Show answer

    2

What next?