Degree of a vertex

To compute the degree it is enough to count the edge endpoints falling on the vertex. In a simple graph the degree of \(v\) equals its number of neighbours, and it always satisfies \(0\le \deg(v)\le n-1\) when the graph has \(n\) vertices. A vertex of degree \(0\) is isolated and one of degree \(1\) is called a leaf.

The basic result is the handshaking lemma: the sum of all degrees is \(\sum_{v\in V}\deg(v)=2|E|\), because each edge contributes one unit to each of its two endpoints. It follows that the number of odd-degree vertices is always even.

The lemma works as a filter: a list of numbers can be the degree list of a simple graph only if its sum is even and no degree exceeds \(n-1\). This test is necessary but not sufficient; for instance \(3,3,3,1\) passes both checks and yet matches no simple graph, since three vertices of degree \(3\) reach the fourth.

A common mistake is counting edges instead of endpoints: in a simple graph there is no difference, but in multigraphs a loop counts twice. Degree is the basis for regular graphs (all vertices with the same degree), such as \(K_n\), and for the Eulerian paths studied later.