Vertex-degree questions look elementary, but counting each edge only once, confusing degree 0 with degree 1, or treating every even-sum sequence as graphical changes the answer. Degree 0 identifies an isolated vertex and degree 1 identifies a pendant vertex; handshaking, regular-graph feasibility, and degree-sequence checks handle the remaining traps. Choose an option before opening each explanation, then check the rule you used. Use the GATE CS Exam Preparation page for the wider preparation route around this topic.
The degree toolkit to use on all 12 questions
In a simple undirected graph, deg(v) is the number of edges incident on vertex v. An isolated vertex has degree 0, while a pendant vertex has degree 1. In a k-regular graph, every vertex has degree k. With n vertices, the largest possible degree is n-1 because a vertex cannot connect to itself.
The Handshaking Lemma says sum deg(v) = 2|E|. Every edge contributes once at each endpoint, so the degree sum is even. Consequently, the number of odd-degree vertices must also be even. This parity also controls whether an Euler trail can exist.
For V={A,B,C,D,E,F} and E={AB,AC,BC,CD,DE}, the degrees are deg(A)=2, deg(B)=2, deg(C)=3, deg(D)=2, deg(E)=1, and deg(F)=0. Thus E is pendant and F is isolated. The sorted sequence is (3,2,2,2,1,0), and 3+2+2+2+1+0=10=2 x 5.
For any proposed degree sequence, first check that every entry lies in [0,n-1], then check that the sum is even. Passing both checks does not guarantee graphicality. Havel-Hakimi is the deciding reduction when these quick filters pass. For maximum-degree bounds, minimum-degree contradictions, and full Havel-Hakimi reductions, use Minimum and Maximum Degree MCQs: 11 Solved Degree Constraints and Havel-Hakimi Questions.
Questions 1-2: maximum degree and complete handshakes
Question 1
What is the maximum degree of any vertex in a simple graph with n vertices?
A. n + 1
B. 2n - 1
C. n
D. n - 1Answer: option D, n - 1.
A vertex can meet the other n-1 vertices, but not itself. For n=6, the maximum is 5=6-1. The answer n would need a self-loop or an extra vertex. Solved page.
Question 2
At the end of a business conference the ten people present all shake hands with each other once. How many handshakes will there be altogether?
A. 20
B. 45
C. 55
D. 90Answer: option B, 45.
Each handshake is an unordered pair, so C(10,2)=10 x 9 / 2=45. In the graph model, ten degree-nine vertices give sum 90, hence 90/2=45 edges. Option 90 counts each handshake at both endpoints. Solved page.
Questions 3-4: parity and regular-graph feasibility
Question 3
Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
A. P only
B. Q only
C. Both P and Q
D. Neither P nor QAnswer: option C, Both P and Q.
Each edge contributes at both endpoints, so the total is 2|E|; Q is true. An odd number of odd-degree terms would make that total odd, so P is true. In (3,3,2,2,2,2), the sum is 14 and two entries are odd. Apply this parity in Graph Theory MCQs: 12 Solved Euler, Coloring, Trees. Solved page.
Question 4
A simple undirected graph G has 24 edges, and every vertex has degree K. Which of the following is a possible number of vertices?
A. 20
B. 15
C. 10
D. 8Answer: option D, 8.
Here nK=2|E|=48. For n=20,15,10, the values 48/n are not integers. For n=8, K=6, and 6<=8-1. Existence also holds: remove a perfect matching from K8, leaving every vertex with degree six. Solved page.
Questions 5-6: repeated degrees and isolated vertices
Question 5
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
A. No two vertices have the same degree.
B. At least two vertices have the same degree.
C. At least three vertices have the same degree.
D. All vertices have the same degree.Answer: option B, At least two vertices have the same degree.
In a connected simple graph, degrees lie in 1,2,...,n-1. These n-1 values serve n vertices, so pigeonhole forces a repeat. A three-vertex path has degrees (2,1,1), proving that at least three equal degrees is too strong. Solved page.
Question 6
The 2ⁿ vertices of a graph G correspond to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of vertices of degree zero in G is:
A. 1
B. n
C. n+1
D. 2ⁿAnswer: option C, n+1.
The empty set and n singletons cannot intersect any set in two elements, so they are isolated. Every larger subset has a distinct neighbour sharing exactly a chosen pair. No vertex is pendant for n>=6: even a two-element subset has 2^(n-2)-1 neighbours, which is at least 15. For n=6, the empty set plus six singletons gives 7=n+1. Solved page.
Questions 7-8: degree sequences and impossible degree counts
Question 7
Consider the following given degree sequences (d₁,d₂,d₃……dₙ) is graphical if there exist a simple undirected graph with n vertices and having the degree sequences:
D1: (3¹,3²,3³,3⁴,3⁵,3⁶,3⁷,3⁸)
D2: (1⁰,2⁰,3⁰,4⁰,5⁰,6⁰,7⁰,8⁰)
Which of the following sequences given is graphical?
A. Both D1 and D2
B. Only D1
C. Only D2
D. None of the aboveAnswer: option C, Only D2.
D1 expands to (3,9,27,81,243,729,2187,6561). Its entries exceed the maximum degree seven for eight vertices, although its sum is even. D2 is (1,1,1,1,1,1,1,1), realised by four disjoint edges. Only D2 is graphical, showing that even sum is necessary but insufficient. Solved page.
Question 8
Consider the following statements.
S1: There is no graph G with VG=12 and EG=28 in which each vertex is of degree either 3 or 4
S2: There is no graph G with VG=12 and EG=28 in which each vertex is of degree either 3 or 6
A. Only S1 true
B. Only S2 true
C. Both of them true
D. Both of them are falseAnswer: option C, Both of them true.
The degree sum must be 2 x 28=56. For S1, 4x+3(12-x)=36+x=56 requires x=20, impossible. For S2, 6y+3(12-y)=36+3y=56 requires non-integer y=20/3. Neither graph exists. Solved page.
Questions 9-10: minimum-degree bounds and attainability
Question 9
G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is:
A. 12
B. 14
C. 16
D. 18Answer: option C, 16.
Here sum deg(v)=2 x 25=50. Since every degree is at least three, 3n<=50, so n<=16. Attain it with cycle C16, eight matching edges (0,8),(1,9),...,(7,15), and chord (0,2). The 25 edges give degrees four at 0,2 and three elsewhere. Solved page.
Question 10
For a simple undirected graph with 4 edges, the maximum possible value of the minimum degree is 2. How many non-isomorphic graphs achieve this value?
A. 1
B. 15
C. 10
D. Data insufficientAnswer: option A, 1.
Four edges give degree sum eight. Minimum degree two implies 2n<=8, so n<=4. Three vertices cannot support four simple edges, hence n=4, all degrees are two, and the graph is C4. It is unique up to isomorphism. C(6,4)=15 ignores the minimum-degree condition. Solved page.
Questions 11-12: a full degree equation and paths between odd vertices
Question 11
What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?
A. 10
B. 11
C. 18
D. 19Answer: option D, 19.
There are n-9 degree-three vertices. Thus 6 x 2 + 3 x 4 + (n-9) x 3 = 3n-3. Set 3n-3=2 x 27=54, obtaining n=19. Check: ten degree-three vertices give 30, and 12+12+30=54. Solved page.
Question 12
Which of the following statements is/are true?
S1: There exists a simple disconnected graph with n vertices where degrees of all vertices are distinct (n>1)
S2: If there are exactly two vertices of odd degree in a simple graph then there must exist a path between those two odd vertices.
A. S1 only
B. Both S1 and S2
C. S2 only
D. Neither S1 nor S2Answer: option C, S2 only.
S1 is false. Distinct degrees would be 0,1,...,n-1, but degree zero and degree n-1 cannot coexist. S2 is true because each component has an even number of odd-degree vertices. With only two in the graph, both are in one component, so a path connects them. Solved page.
Diagnose the error pattern and choose the next practice set
If Questions 2, 3, 4, 8, 9, 10, or 11 went wrong, write sum deg(v)=2|E| before any arithmetic. For Questions 5 or 12, revise the pigeonhole and parity consequences. For Question 6, classify degree-zero and degree-one vertices first. For Question 7, check both the degree range and realisability.
Use Discrete Mathematics MCQs as the subject-wide next set, or GATE Guidance by Sanchit Sir for the full teaching sequence. Now redo all 12 without opening the explanations, note the rule behind every miss, and practise this subtopic again after two days.
