Lesson 20 of 1524
Graph theory
The degrees of a graph add up to twice the number of edges.
Practice this chapterA graph is vertices joined by edges. The degree of a vertex counts the edges that meet it. Each edge contributes to two degrees, one at each end, so the sum of the degrees is 2E.
A connected graph has a circuit that uses every edge exactly once exactly when every degree is even. That circuit is an Euler circuit. Zero or two odd degrees allows an Euler path that is not a closed circuit.
Handshaking lemma
sum of degrees = 2E
The number of edges is half the sum of the degrees.
Worked example
Four vertices have degrees 2, 2, 2, and 2. How many edges are there, and is an Euler circuit possible?
- 1Each edge meets two vertices, so it is counted in two degrees. The handshaking lemma says the degree sum equals 2E.
- 22 + 2 + 2 + 2 = 8, so 2E = 8 and E = 4.
- 3An Euler circuit uses every edge once and returns to the start. In a connected graph, that exists exactly when every degree is even.
- 4Every degree here is 2, which is even. The circuit exists if this graph is also one connected piece. The degrees alone do not prove that it is connected.
Result: 4 edges. Yes, if the graph is connected.
Why. Four edges follow because half of the degree sum is the edge count. An Euler circuit needs those even degrees and a connected graph. Even degrees with the graph in two separate pieces would not give one circuit through every edge.
An Euler circuit covers every edge. A Hamilton circuit covers every vertex. The tests are not the same.
Practice margin
This chapter
A fresh set from this chapter only. Choose 10 or 20. Multiple choice and fill-in, with no repeat inside the set.