Bipartite, Cycle, Regular and Complement Graph MCQs: 12 Solved Questions

These graph MCQs reuse a few identities, but a missed qualifier such as complete, bipartite, regular, cycle or complement changes the count. Most of the twelve questions below turn on which of four counts applies: a two-colouring, a product of part sizes, a degree sum, or the total number of vertex pairs. On six vertices the cycle C6 has 6 edges, its complement has 9, and there are 15 vertex pairs in all, so the count you reach for decides the answer. Settle that first, then read the options. Each question heading opens that question's own practice page, and this subtopic's practice set runs to over 30 questions inside the broader GATE CS preparation collection.

1. Put the four graph ideas on one six-vertex example

Take cycle C6 with V={1,2,3,4,5,6} and E={12,23,34,45,56,61}. Colour X={1,3,5} blue and Y={2,4,6} orange. Every edge crosses the sets, so it is bipartite. Its length 6 is even, and every vertex has degree 2, making C6 2-regular.

Of C(6,2)=6x5/2=15 unordered vertex pairs, the cycle uses 6, so its complement has 15-6=9 edges. Each complement degree is (6-1)-2=3; the degree-sum check gives 6x3/2=9 edges. Those nine edges are the two triangles 135 and 246 plus the three long diagonals 14, 25 and 36, so the complement of C6 is a triangular prism. It is not K3,3, even though both have nine edges and every degree 3.

On the same parts, replace C6 with K3,3. All 3x3=9 cross-partition edges are present, giving every vertex degree 3. C6 uses two cross edges per vertex; K3,3 adds the rest, raising each degree from 2 to 3. Four rules cover most of this set:

• A graph is bipartite if and only if it has no odd cycle.

• K(a,b) has ab edges.

• A d-regular graph on n vertices has nd/2 edges.

• A simple graph satisfies |E(complement of G)|=C(n,2)-|E(G)|.

The Discrete Mathematics MCQs hub places these rules beside questions from the rest of the subject.

2. Questions 1-2: cycle degree and the bipartite parity test

Question 1

In a graph with n vertices, what is the degree of each vertex in a cycle graph?

• A. 1

• B. 2

• C. n

• D. n-1

Correct answer: B. 2.

In C_n, each vertex meets two cycle edges: one to its predecessor and one to its successor. In C6, vertex 1 meets 12 and 61, so deg(1)=2. Every vertex follows this pattern; increasing n lengthens the cycle without changing the degree.

Question 2

A bipartite graph can have:

• A. only odd cycles

• B. Only even cycles

• C. Both odd and even cycles

• D. Only odd cycles

Correct answer: B. Only even cycles.

Alternating the two colours around a cycle, an even number of edges returns to the starting colour; an odd number would assign it both colours. Thus every cycle in a bipartite graph is even. Options A and D print the same claim here, and both fail, because an odd cycle is exactly what a two-colouring rules out. A tree remains bipartite despite having no cycle.

Next, use Graph Theory MCQs: 12 solved questions on Euler paths, coloring and trees for Euler, colouring and tree questions.

3. Questions 3-4: maximise edges by balancing the two parts

Question 3

Asked in HPSC 2021, Computer Science.

What is the maximum number of edges in a bipartite graph having 10 vertices?

• A. 24

• B. 21

• C. 25

• D. 16

Correct answer: C. 25.

If the parts have sizes a and 10-a, the complete bipartite graph contains a(10-a) edges. The balanced split gives 5x5=25; its neighbours give 4x6=24 and 3x7=21. Hence 25 is the maximum.

Question 4

What is the maximum number of edges in a bipartite graph with n even vertices ?

• A. n²

• B. 2n-4

• C. 2n

• D. n²/4

Correct answer: D. n²/4.

For even n, choose two equal parts of n/2 vertices and include every cross edge. The count is (n/2)(n/2)=n²/4. With n=12, K6,6 has 6x6=36 edges, equal to 12²/4=36. Moving one vertex produces a 5,7 split and only 5x7=35 edges.

4. Questions 5-7: complete bipartite counting and a matching certificate

Question 5

Asked in UGC NET December 2008, Paper 2.

The graph K₃,₄ has:

• A. 3 edges

• B. 4 edges

• C. 7 edges

• D. 12 edges

Correct answer: D. 12 edges.

In K3,4, each of the 3 vertices in one part connects to all 4 in the other, giving 3x4=12 edges. The degree sum confirms it: 3x4+4x3=24, then 24/2=12 edges.

Question 6

Asked in TCS 2025.

In a meeting between 2 countries each country has 12 delegates. All the delegates of one country shake hands with all delegates of other countries. Find the number of handshakes possible ?

• A. 72

• B. 144

• C. 288

• D. None

Correct answer: B. 144.

Model the countries as two parts of 12 vertices. The cross-country pairs total 12x12=144. Do not halve the result because each pair was generated once, and do not double it because a handshake has no direction.

Question 7

Asked in MPPSC 2025.

In the decision version of the minimum vertex cover problem in a bipartite graph, if the answer is "No", what serves as a valid No certificate?

• A. A matching of size K + 1

• B. A vertex cover of size K - 1

• C. An edge not included in the cover

• D. A subgraph with no matchings

Correct answer: A. A matching of size K + 1.

A matching contains vertex-disjoint edges, and a vertex cover needs one endpoint from every matched edge. Thus a matching of size K+1 proves that no cover of size at most K exists. For K=3, four disjoint edges force at least four selected vertices.

5. Questions 8-9: regular-graph edge counts and the one regular wheel

A d-regular graph is one in which every vertex has degree d. With n vertices, its degree sum is nd. The handshaking lemma counts every edge twice in that sum, so 2|E|=nd.

Question 8

Asked in UPLT 2026.

The number of edges in a regular graph of degree 'd' and 'n' vertices is:

• A. nd

• B. (nd)/2

• C. n+d

• D. maximum of n, d

Correct answer: B. (nd)/2.

From 2|E|=nd, divide both sides by 2 to get |E|=nd/2. For n=8,d=3, the degree sum is 8x3=24, so the graph has 24/2=12 edges. A simple d-regular graph can exist only when nd is even, since its edge count must be an integer.

Question 9

Asked in UGC NET 2021.

For which value of n is Wheel graph Wn regular?

• A. 2

• B. 3

• C. 4

• D. 5

Correct answer: B. 3.

Under the convention used in this question, W_n adds one hub to C_n. A rim vertex has degree 3 and the hub has degree n, so regularity requires n=3. Then W3 is K4, with every degree equal to 3. In W4, the hub degree is 4 while each rim degree is 3. Other books may index by total vertex count.

6. Questions 10-12: complement edge counts from all possible pairs

Question 10

A graph G and its complement Ḡ have 8 and 7 edges respectively. Then the number of vertices in G is

• A. 6

• B. 5

• C. 8

• D. none of these

Correct answer: A. 6.

A simple graph and its complement split all possible unordered pairs, so C(n,2)=8+7=15. Therefore n(n-1)/2=15, or n(n-1)=30. The consecutive factors are 6x5, giving n=6. As a check, 5 vertices allow only 10 pairs and 8 vertices allow 28.

Question 11

What is the complement of a complete graph with n vertices?

• A. Empty Graph

• B. Complete Graph

• C. Cycle Graph

• D. Tree

Correct answer: A. Empty Graph.

K_n contains every edge between distinct vertices. Its complement keeps the vertices but has no edges. For K4, the possible count is C(4,2)=6, so the complement has 6-6=0 edges and four isolated vertices.

Question 12

If a simple graph G contains n vertices and m edges, the number of edges in the complement graph G' (the complement of G) is ___________

• A. (n² − n − 2m) / 2

• B. (n² + n + 2m) / 2

• C. (n² + n − 2m) / 2

• D. (n² − n + 2m) / 2

Correct answer: A. (n² − n − 2m) / 2.

Begin with C(n,2)-m=n(n-1)/2-m. A common denominator gives (n²-n-2m)/2, option A. For n=8,m=12, the complement has C(8,2)-12=28-12=16 edges. The formula agrees: (64-8-24)/2=32/2=16. Complementing subtracts m; it never adds it.

7. Check your answers, repair the missed invariant, and continue

Answer key: 1-B, 2-B, 3-C, 4-D, 5-D, 6-B, 7-A, 8-B, 9-B, 10-A, 11-A, 12-A. For each miss, record the failed cue.

Redo in 20 minutes: 10 to answer all 12, 6 to redraw C6 and its complement and recompute its 6 cycle edges, the 9 complement edges and the degrees 2 and 3, then 4 to record each first mistaken inference. Retest the misses the next day.

The short version

Bipartite means no odd cycle. Complete bipartite means multiply the part sizes. Regular means use the degree sum. Complement means subtract existing edges from all C(n,2) pairs. Graph Theory: Euler and Hamiltonian Paths, Coloring and Connectivity is the next theory step.

Use GATE Guidance by Sanchit Sir for structured study and the GATE Test Series for timed practice. Carry the four-rule checklist into every graph question.