Degree of a vertex and handshaking lemma
Graph theory · Mathematics
Study notes
Q: Can a graph have degrees 1, 2, 3, 4, 5? Justify. Sum = 1+2+3+4+5 = 15 - odd! Handshaking: Σ deg = 2|E| must be even. 15 is odd, so NO such graph exists. But 1,2,3,4,6 sums to 16 = 2×8: possible in principle!