Vertex cover, independent set, line or edge cover, minimum, minimal, maximum, and maximal sound interchangeable, but they answer different questions. A vertex cover hits every edge, an independent set avoids every edge, and each one is the complement of the other, so a single number hands you both. The eleven questions below run from the Four Colour bound on planar graphs to the Petersen graph, complete bipartite covers, and two numericals. Commit to an answer before reading each explanation, then use the reasoning to check it.
1. Build the concept map before attempting the MCQs
A vertex cover is a set of vertices that meets every edge. An independent set has no edge between any two selected vertices. A line cover, also called an edge cover, is a set of edges incident on every vertex.
The key complement identity is
tau(G) + alpha(G) = |V|,
where tau(G) is the minimum vertex-cover size and alpha(G) is the maximum independent-set size. For a graph without isolated vertices, the different edge-cover identity is rho(G) = |V| - nu(G), where nu(G) is the maximum matching size.
Warm up with the path P4: v1-v2-v3-v4:
{v2,v3}is a minimum vertex cover, sotau=2.{v1,v3}is a maximum independent set, soalpha=2.{v1v2,v3v4}is a maximum matching, sonu=2.The same two edges cover all four vertices, so
rho=4-2=2.
Minimum and maximum optimise size. Minimal means no selected element can be removed while preserving the property; maximal means no new element can be added. For the broader subject sequence, use GATE Guidance by Sanchit Sir. The GATE CS exam category is the wider preparation path.
2. Questions 1-3: planar bounds and independent-set basics
Question 1
Which of the following statements is true for every planar graph on n vertices?
A. The graph has a vertex-cover of size at most 3n/4
B. The graph is Eulerian
C. The graph is connected
D. The graph has an independent set of size at least n/3
Answer: A. The Four Colour Theorem partitions the vertices into four independent colour classes. One class contains at least n/4 vertices, and its complement is a vertex cover of size at most n-n/4=3n/4. For D, planar K4 is a counterexample: alpha(K4)=1, which is less than 4/3. Planarity guarantees neither connectivity nor all-even degrees.
Question 2
An independent set in a graph is a set of vertices:
A. That are all adjacent
B. That are all connected
C. No two of which are adjacent
D. That form a cycle
Answer: C. For every two selected vertices u and v, uv must not be an edge. A clique is the opposite pattern, since every pair in a clique is adjacent.
Question 3
Find the minimum number of independent sets for the following graph.
Numerical answer type, so no options are listed. Find the largest set of pairwise adjacent vertices first, because it fixes the lower bound.
Answer: 3. The triangle on D,C,E requires at least three independent sets. The partition {A,C}, {B,D}, and {E,F,G} covers all seven vertices, and no listed pair inside any set is adjacent. The lower bound is therefore achievable.
3. Questions 4-5: recognise a vertex cover and force a vertex into every minimum cover
Question 4
A vertex cover of an undirected graph G(V, E) is a subset V₁ ⊆ V of vertices such that
A. Each pair of vertices in V₁ is connected by an edge
B. If (u, v) ∈ E then u ∈ V₁ and v ∈ V₁
C. If (u, v) ∈ E then u ∈ V₁ or v ∈ V₁
D. All pairs of vertices in V₁ are not connected by an edge
Answer: C. Every edge needs at least one endpoint in the chosen set. The “or” is inclusive, so one or both endpoints may belong to the cover. Option B demands both endpoints and is stronger than the definition.
Question 5
Let G(V,E) be a simple, undirected graph. A vertex cover of G is a subset V'⊆V such that for every (u,v)∈E, u∈V' or v∈V'. Let the size of the smallest vertex cover in G be k. Let S be any vertex cover of size k. For a vertex v∈V, which of the following constraints will always ensure that v∈S?
A. The degree of v is at least k+1
B. The vertex v is on a path of length k+1
C. The vertex v is on a cycle of length k+1
D. The vertex v is a part of a clique of size k
Answer: A only. If v were excluded, all its neighbours would have to be in S. Degree at least k+1 would then require more than k vertices. B fails on P3 with k=1: an endpoint lies on a length-2 path but the middle vertex alone is a minimum cover. C fails on a triangle with k=2, where any named vertex can be excluded. D fails in K_(k+1): v belongs to a k-clique, yet V\{v} is a minimum cover.
4. Questions 6-8: Petersen structure, complete bipartite covers, and connectivity
Question 6
The following simple undirected graph is referred to as the Petersen graph.
Which of the following statements is/are TRUE?
A. The chromatic number of the graph is 3.
B. The graph has a Hamiltonian path.
C. The following graph is isomorphic to the Petersen graph.
D. The size of the largest independent set of the given graph is 3.
Answer: A, B, and C. A 5-cycle rules out two colours, while a 3-colouring exists. The Petersen graph has no Hamiltonian cycle but does have a Hamiltonian path. The second drawing also has ten vertices, every vertex of degree three, and no cycle shorter than five, and the Petersen graph is the only graph with all three properties, so C holds. D is false because its independence number is 4, not 3. Check that on the first drawing: two outer vertices that are not neighbours, plus two inner vertices that the star does not join, already give an independent set of four.
Question 7
Let Km,n be the complete bipartite graph with m+n vertices. Determine the vertex covering number of Km,n.
A. m+n
B. |m-n|
C. Minimum (m, n)
D. Maximum (m, n)
Answer: C, min(m,n). Taking every vertex on the smaller side covers every cross-edge. A matching can pair every vertex on that side with a distinct vertex on the other side, producing min(m,n) disjoint edges. Every vertex cover needs an endpoint from each, so no smaller cover exists.
Question 8
Consider the following network represented as a graph in which each node is a station and each edge is a link between the stations. Find the maximum number of links that can be deleted while still allowing the stations to communicate with each other.
Numerical answer type, so no options are listed. Count the vertices and the links in the figure before you subtract anything.
Answer: 5. The graph has 9 vertices and 13 edges. A connected spanning subgraph needs at least 9-1=8 edges. The eight edges {ab,bd,de,ec,ef,fg,gh,hi} form a spanning tree, while {ac,bc,cd,cf,fi} are the other five edges. Therefore the maximum deletion count is 13-8=5.
5. Questions 9-11: colouring bounds, smallest maximal sets, and the complement identity
Question 9
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let G be any graph with n vertices and chromatic number k. Which of the following statements is/are always TRUE?
A. G contains a complete subgraph with k vertices
B. G contains an independent set of size at least n/k
C. G contains at least k(k-1)/2 edges
D. G contains a vertex of degree at least k
Answer: B and C. The largest of k colour classes has at least ceil(n/k) vertices and is independent. A k-chromatic graph contains a k-critical subgraph with minimum degree at least k-1. That subgraph has at least k vertices, so it has at least k(k-1)/2 edges. The cycle C5 has k=3, clique number 2, and every degree equal to 2, rejecting A and D.
Question 10
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
A. 5
B. 4
C. 3
D. 2
Answer: C, 3. Number the path vertices 1 to 9. The set {2,5,8} is independent and dominates every unselected vertex, so it is maximal. Two selected path vertices can cover at most themselves and four neighbours, only six vertices, so two cannot dominate all nine. This smallest maximal set has size 3; a maximum independent set has size 5, for example {1,3,5,7,9}.
Question 11
Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is
A. 12
B. 8
C. Less than 8
D. More than 12
Answer: A, 12. Apply alpha(G)+tau(G)=|V|: alpha=20-8=12. The 100 edges are distractor data. Once the minimum vertex-cover size is known, the edge count is unnecessary.
6. Reduce the set to four reusable moves
Move | Use it in | What to do |
|---|---|---|
Take the complement | Q1, Q11 | Switch between a vertex cover and an independent set. |
Partition into independent colour classes | Q3, Q9 | Use a clique for a lower bound and a valid partition for construction. |
Prove a lower bound, then exhibit a construction | Q7, Q8, Q10 | Match the bound with an explicit cover, tree, or maximal set. |
Test the exact quantifier | Q2, Q4, Q5 | Check every pair, every edge, or every minimum cover exactly as stated. |
Q6 is the visual-structure exception: isomorphic drawings can look different while preserving adjacency.
Keep four corrections ready. A minimum set is not merely minimal. A maximum independent set is not a smallest maximal independent set. Isomorphic graphs need not look alike. A connected graph can lose edges only until a spanning tree remains, never below n-1 edges. Use the mixed Graph Theory MCQ collection as the next drill once those four corrections feel automatic.
7. Short version and next step
Remember this chain: vertex cover <-> complement independent set, colour class -> independent set, connected minimum -> spanning tree, and maximal means cannot add, maximum means largest. The three worked values are Q3 = 3 independent sets, Q8 = 5 deletions, and Q11 = 20-8=12.
If you missed definition questions, revisit the Discrete Mathematics MCQ hub. If the numerical or multiple-select questions caused trouble, practise under time pressure in the GATE Test Series. Then redo Q5, Q8, and Q10 without looking. Together they test forced membership, spanning-tree deletion, and smallest maximal versus maximum independent set.
