Degree of a Vertex in Graph: Definition, Examples, Handshaking Theorem

In graph theory, the degree of a vertex is the number of edges connected to it. In this article, we will study the degree of a vertex in a graph with its definition, examples, and related theorems, such as Handshaking lemma.

Degree of a Vertex

Definition: In an undirected graph, the number of edges connected to a vertex is called the degree of that vertex.

A loop at a vertex contributes twice to the degree of that vertex.

The degree of a vertex v in a graph G is denoted by deg(v).

Examples

Let us consider the following graph.

Degree of a vertex Example

In the above graph, we observe that there are two edges connected to v1 and there are three edges connected to v2. Therefore,

deg(v1) = 2 and deg(v2) = 3.

Similarly, deg(v3) = 3, deg(v4) = 1, deg(v5) = 3, deg(v6) = 2, deg(v7) = 0.

Thus, v4 is a pendant vertex and v7 is an isolated vertex.

Properties

The degree of a vertex of a graph has the following properties.

  1. The degree of an isolated vertex is 0.
  2. If a vertex has a loop incident with it, then it contributes twice to the degree of the vertex.
  3. If the degree of a vertex is 1, then it is called a pendant vertex.
  4. The sum of the degrees of all vertices is equal to two times the number of edges. This is known as the Sum of Degree Theorem.
  5. In an undirected graph, the number of vertices of odd degree is even.

Handshaking Theorem

Statement: If G=(V, E) is an undirected graph having e edges, then we have

viVdeg(vi)=2e.

That is, the sum of the degrees of all vertices = 2 times the number of edges. This Theorem is also known as the Degree Sum Theorem or the Handshaking Lemma.

Proof of Handshaking Theorem

We know that each edge is connected with exactly two vertices. This ensures that each edge contributes 2 to the sum of the degrees of all vertices.

Therefore, it follows that

viVdeg(vi)=2e.

This completes the proof of the Handshaking Theorem.

Theorem

Prove that the number of vertices of odd degree in a graph is always even.

Let G = (V, E) be an undirected graph.

Let us consider the two sets defined by

V1:= The set of vertices of G of even degree.

V2:= The set of vertices of G of odd degree.

By Handshaking theorem, we have

viVdeg(vi)=2e

viV1deg(vi)+viV2deg(vi)=2e.

By definition, the sum viV1deg(vi) is even. Therefore, we deduce that viV2deg(vi) is also even.

As each deg(vi) is odd, for each vi ∈ V2, viV2deg(vi) is even implies that the number of vertices of odd degree is even.

Also Read:

Homepage of Discrete Mathematics

FAQs

Q1: What is handshaking lemma?

Answer: The handshaking lemma states that the sum of the degrees of all vertices in a graph is equal to 2 times the number of edges.

Share via: