SKEDSOFT

Handshaking Lemma: The sum of the degrees of the vertices in a graph is twice the number of edges.

If G = (v, E) be an undirected graph with e edges.
Then

i.e., the sum of degrees of the vertices is an undirected graph is even.

Proof : Since the degree of a vertex is the number of edges incident with that vertex, the sum of the degree counts the total number of times an edge is incident with a vertex. Since every edge is incident with exactly two vertices, each edge gets counted twice, once at each end. Thus the sum of the degrees equal twice the number of edges.

Note : This theorem applies even if multiple edges and loops are present. The above theorem holds this rule that if several people shake hands, the total number of hands shake must be even that is why the theorem is called handshaking theorem.

Corollary : In a non directed graph, the total number of odd degree vertices is even.

Proof : Let G = (V, E) a non directed graph.
Let U denote the set of even degree vertices in G and W denote the set of odd degree vertices.

∴ The no. of odd vertices in G is even.
Theorem. If V = {v1, v2, ...... vn} is the vertex set of a non directed graph G,

If G is a directed graph, then

Proof : Since when the degrees are summed. Each edge contributes a count of one to the degree of each of the two vertices on which the edge is incident.
Corollary (1) : In any non directed graph there is an even number of vertices of odd degree.
Proof : Let W be the set of vertices of odd degree and let U be the set of vertices of even degree.

Hence is even,

Implying that | W | is even.

Corollary (2) : If k = δ(G) is the minimum degree of all the vertices of a non directed graph G, then

In particular, if G is a k-regular graph, then