Minimum and Maximum Degree MCQs: 11 Solved Degree Constraints and Havel-Hakimi Questions

Even degree sums are necessary, not sufficient; Havel-Hakimi decides whether a surviving sequence is graphical.

Almost every degree question falls to one of four moves: the ceiling on a single degree, the Handshaking Lemma, an edge bound built from the largest or smallest degree, and a Havel-Hakimi reduction. Choose an answer and write one check before you read each explanation. Use GATE CS Exam Preparation as the wider study route.

Degree bounds and Havel-Hakimi: the four checks that settle these questions

For a simple undirected graph on n vertices, 0≤deg(v)≤n-1. The Handshaking Lemma gives Σdeg(v)=2|E|; hence the total degree and the number of odd-degree vertices are even. A maximum degree Δ gives 2|E|≤nΔ, while a minimum degree δ gives 2|E|≥nδ.

For n=7 and Δ≤3, 2|E|≤21; the largest even value is 20, so |E|≤10, not 10.5. This is attainable: (3,3,3,3,3,3,2) sums to 20 and passes Havel-Hakimi.

Havel-Hakimi removes the largest degree, decrements that many entries, and re-sorts. For example, (4,3,3,2,2) → (2,2,1,1) → (1,1) → (0,0); all zeros certify graphicality. Reject a leader exceeding the remaining count or any negative subtraction. These checks sit beside the other tools in Graph Theory: Euler, Hamiltonian, Coloring for GATE CS.

Questions 1-3: maximum degree, edge caps and a minimum-degree bound

Question 1 (CoCubes 2023, Computer Science)

Maximum degree of any vertex in a simple graph of vertices n is

A. 2n - 1
B. n
C. n + 1
D. n - 1

Answer: option D, n - 1.

A simple graph has no self-loop and permits one edge from a vertex to each of the other n-1 vertices. For n=6, the maximum degree is 5, never 6; loops or parallel edges leave the model.

Question 2: maximum edges under a degree cap

If G is a simple graph with 11 vertices and degree of each vertex is atmost 5, then maximum number of edges possible in G is

A. 26
B. 27
C. 27.5
D. 29

Answer: option B, 27.

The cap gives Σdeg(v)≤11×5=55. Handshaking makes 54 the largest usable sum, so |E|≤27. The sequence (5,5,5,5,5,5,5,5,5,5,4) passes Havel-Hakimi, proving attainability.

Question 3: maximum vertices from a minimum degree

Maximum number of vertices possible in a simple graph if 35 edges and degree of each vertex is at least 3 is _____?

Answer: 23.

Here 2|E|=70≥3n, so n≤⌊70/3⌋=23. To attain it, label vertices 0,...,22, take C23, add (0,11),(1,12),...,(10,21), then (22,10). This gives 23+11+1=35 edges; vertex 10 has degree 4 and all others degree 3.

Questions 4-6: Handshaking consequences and unknown degrees

Question 4: consequences of the Handshaking theorem

What Conclusions may be drawn from the Handshaking theorem?

A. The Sum of degrees of all vertices is always even.
B. The Sum of degrees of all vertices with odd degree is always even.
C. The number of vertices with odd degree is always even
D. none of above

Answer: options A, B and C.

Because Σdeg(v)=2|E|, option A holds. Removing the even-degree contributions leaves an even odd-degree sum, proving option B. Such a sum has an even number of odd terms, proving option C. In (3,3,2,2,2), the total is 12, the odd-degree sum 6, and the odd-vertex count 2.

Question 5: solve for two unknown degrees

Consider the following degree sequence:
5, p, 4, 4, 3, q, 2, 1. The given sequence is valid for a connected graph and the number of edges is 13, then find the possible values of p and q.

A. 5,2
B. 6,4
C. 4,3
D. 6,1

Answer: options A, C and D.

The total is 2×13=26; known degrees sum to 19, so p+q=7. Options A, C and D pass, while option B totals 29. Havel-Hakimi confirms (5,5,4,4,3,2,2,1) → ... → (0,0), (5,4,4,4,3,3,2,1) → ... → (0,0) and (6,5,4,4,3,2,1,1) → ... → (0,0). Each has a connected realization; the equation alone does not prove graphicality.

Question 6 (GATE 2017, Computer Science, Set 2)

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 _________ .

Answer: 16.

Here Σdeg(v)=2×25=50≥3n, so n≤16. Take C16 and add (0,8),(1,9),...,(7,15), making a 3-regular graph with 16+8=24 edges. Add (0,2) for 25 edges: vertices 0 and 2 have degree 4, the other 14 degree 3.

For adjacent mixed practice, use Graph Theory MCQs: 12 Solved Euler, Coloring, Trees.

Questions 7-8: rejecting an impossible sequence and certifying a valid one

Question 7: invalid connected-graph sequences

Which of the following degree sequence diagrams are invalid for a connected graph with 6 vertices?

A. 5,5,3,2,2,1
B. 6,5,4,3,2,1
C. 2,2,2,2,1,1
D. 5,4,3,2,2,1

Answer: options A, B and D.

Option B has degree 6>5 and odd sum 21; option D has odd sum 17. Option A totals 18, but (5,5,3,2,2,1) → (4,2,1,1,0), then removing 4 creates a negative entry. Option C is path P6, hence valid and connected.

Question 8: a complete successful Havel-Hakimi reduction

Does the degree sequence 6, 5, 5, 5, 4, 4, 2, 1 violate the Havel-Hakimi criterion?

A. True
B. True, but only after sorting
C. False
D. None of the above

Answer: option C, False.

The sorted reduction is (6,5,5,5,4,4,2,1) → (4,4,4,3,3,1,1) → (3,3,2,2,1,1) → (2,1,1,1,1) → (1,1,0,0) → (0,0,0). No leader is too large and no subtraction is negative, so it is graphical. Sorting is normal, not a reason to select option B.

Questions 9-11: graphical tuples and a minimum-degree contradiction

Question 9 (GATE 2014, Computer Science, Set 1)

An ordered n-tuple (d1, d2, ..., dn) with d1 ≥ d2 ≥ ... ≥ dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, ..., dn respectively. Which one of the following 6-tuples is NOT graphic?

A. (1, 1, 1, 1, 1, 1)
B. (2, 2, 2, 2, 2, 2)
C. (3, 3, 3, 1, 0, 0)
D. (3, 2, 1, 1, 1, 0)

Answer: option C, (3, 3, 3, 1, 0, 0).

It reduces (3,3,3,1,0,0) → (2,2,0,0,0); subtracting from 2 and 0 then creates a negative entry. Option A is three disjoint edges and option B is C6. Option D reduces (3,2,1,1,1,0) → (1,1,0,0,0) → (0,0,0,0).

Question 10 (GATE 2010, Computer Science)

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1       II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2     IV. 8, 7, 7, 6, 4, 2, 1, 1

A. I and II
B. III and IV
C. IV only
D. II and IV

Answer: option D, II and IV.

IV is impossible because degree 8 exceeds the ceiling 7. II reduces (6,6,6,6,3,3,2,2) → (5,5,5,2,2,2,1) → (4,4,1,1,1,1) → (3,1,0,0,0), where 3 cannot be satisfied. I reduces (7,6,5,4,4,3,2,1) → (5,4,3,3,2,1) → (3,2,2,1) → (1,1) → (0,0). III reduces (7,6,6,4,4,3,2,2) → (5,5,3,3,2,1,1) → (4,2,2,1,1) → (1,1) → (0,0). Thus I and III are graphical.

Question 11 (GATE 2003, Computer Science)

A graph G = (V, E) satisfies |E| ≤ 3|V| - 6. The min-degree of G is defined as the smallest degree(v) over all vertices v in V. Therefore, min-degree of G cannot be

A. 3
B. 4
C. 5
D. 6

Answer: option D, 6.

If δ(G)≥6, then Σdeg(v)≥6|V|, so Handshaking gives |E|≥3|V|, contradicting |E|≤3|V|-6. Degree 5 is not forbidden: 2|E|≥5|V| is compatible with the cap when |V|≥12.

Five traps these degree questions expose

1. Using n instead of n-1. No self-loop.

2. Accepting half an edge. Use 55→54→27.

3. Treating an even sum as proof. Question 7 option A sums to 18 but fails.

4. Reducing too early. Reject 6>5 and 8>7 immediately.

5. Giving only a bound. Question 3 attains it with C23 plus 12 chords; Question 6 with C16, a matching and one chord.

Bounds and parity filter; Havel-Hakimi certifies. A maximum needs a bound and construction.

The short version and the next practice step

• Enforce 0≤d_i≤n-1.

• Use Σd_i=2|E|; keep the sum even.

• Convert degree constraints into bounds on 2|E|.

• Then run Havel-Hakimi.

Solve Questions 1-6 with bounds and parity, then write every reduction for 7-11. Classify misses: ceiling, parity, bound direction, graphicality.

Continue with Discrete Mathematics MCQs for a broader set across the subject. For the structured teaching route, use Engineering Mathematics for GATE Exam.