Counting Degrees & Edges
-
How many edges does a graph have if the degrees of its vertices are 4, 3, 3, 2, and 2?
In every graph, the sum of the degrees equals twice the number of edges. Since 4+3+3+2+2 = 14, we have 7 edges. -
Which of the following must be true for any simple graph \(G\)?
The degree sum must be even by the Handshaking Lemma.
Suppose we had a graph with an odd number of vertices with odd degree. Then by the Handshaking Lemma, the total degree would be the sum of an odd and an even number, giving an odd number. Contradiction!
Consider the complete graph \(K_5\). Each of the 5 vertices has degree 4.