Test: Degree of Vertex - Computer Science Engineering (CSE) MCQ

Data:
For an undirected graph
sum of degree in a graph = d_sum
number of edges in a graph  = e
Formula:
By handshaking lemma:
d_sum = 2 × e
Conclustion:
if e is even
d_sum = 2 × even = even
if e is odd
d_sum = 2 × odd = even
In an undirected graph, if we add the degrees of all vertices, it is even

Concept:
A tree with n vertices has e edges
The Handshaking Theorem states that the sum of the degrees of all the vertices of G is twice the number of edges in G.

Formula:
∑ di  = 2 × e  (By Handshaking  Lemma)

Explanation:
Given an undirected graph total of n edges
e=n
and ∑ di  is the sum of the degree of each vertex
∑ di  = 2 × e
∑ di  = 2n
So, the sum of the degree of each vertex is 2n

Concept

• A graph with no self-loops and no parallel edges is called a simple graph.
• Maximum degree in a simple graph is possible only if it is a complete graph

Example of a complete graph with n= 4

Every vertex has (n-1) degree if n is the number of vertices in a graph
Degree of (A) = Degree(B) = Degree(C) = n - 1 = 4 - 1 = 3

Havel Hakimi procedure:
Sequence I: 4 7 1 6 3 4 6 2

Sequence II: 3 3 3 3 3 3

Sequence III: 5 4 6 7 6 3 6 5

II and III can be possible sequence of degree of some graph.

Concept:
Since there is only one simple path between each pair of vertices, the given graph is a tree.
Tree with n nodes has (n -1) edges
Let the number of vertices of degree 1 be x.
2 vertices have degree 4
2 vertices have degree 2
1 vertex has degree 3

Calculation:
Total number of nodes in a graph = x + 2 + 2 + 1 = x + 5
Total number of edges in a graph = x + 5 - 1 = x + 4
According to Handshaking Lemma,
∑deg(v) = 2|E| where E is Edges.
2×4+1×3+2×2+x=2(x+4)
15 + x = 8 + 2x
∴ x = 7

Data:
|H| = |G| = n = 11
number of edges in H = |E| = y × 2¹⁰

Formula:
By Handshaking Lemma:
Σd_i = 2 × |E|
Where d_i is the degree of i^th vertex  
|E| is the number of edges in a graph

Calculation:
For n-dimensional cube:
Degree of vertices = n = 11
Number of vertices: 2n =2¹¹
11 × 2¹¹ =2 × |E1|
| E1| =11 × 2¹⁰

For complete graph:
Degree of each vertex: 2¹¹ – 1
(2¹¹ − 1) × 2¹¹ = 2 ×|E₂|
| E2|= 2047 × 2¹⁰
E = |E2| – |E1|
y × 2¹⁰ = 2047 × 2¹⁰ – 11 × 2¹⁰
∴ y = 2036

Concept:
By using handshaking theorem of graph theory, the sum of degree of all the vertices in a tree is equal to twice the number of edges in a graph.

Formula:

where di is the degree of vertex i and e is the total number of edges in a graph

Calculation:
For a tree,
number of edges = e = n – 1

sum of the degrees of all the vertices in T is 32.

III is not simple graph as highest degree in any simple graph with n vertices is (n-1). II is also not a simple graph because it has 7 vertices and two vertices has degree 6, hence minimum degree cannot be 1. We can use Havel-Hakimi method for I & IV. We can show II is not simple graph using Havel-Hakimi method also.

The number of edges connected on a vertex v with the self loop counted twice is called the degree of vertex.

A graph in which all vertices are of equal degree is called regular graph.