Graph Covering: Line and Vertex Covers, Independent Sets, Minimal vs Minimum, Maximal vs Maximum
Carry one six-vertex path through vertex covers, independent sets, edge covers and matchings. Exact witnesses show why local irreducibility is not global optimality.
KnowledgeGate Team
Exam prep & CS education

A vertex cover chooses vertices to cover edges, while a line cover chooses edges to cover vertices. The definitions are short, but the words minimal, minimum, maximal and maximum can completely change the answer. The six-vertex path P6 illustrates the central objects, with exact optimal and locally irreducible witnesses. A proposed set can be audited, the right number calculated using complements or matchings, and a merely local answer rejected when the question asks for a global optimum.
1. Graph covering vocabulary: what is selected, and what must be covered?
Let G=(V,E) be a finite, simple, undirected graph. A vertex cover C subseteq V contains an endpoint of every edge; its minimum size is tau(G). An independent set I subseteq V contains no adjacent pair; its maximum size is alpha(G). Some textbooks use different Greek letters, so check the question's notation.
A line cover, or edge cover, is F subseteq E such that every vertex meets a chosen edge; its minimum size is rho(G). A matching has no two edges sharing an endpoint; its maximum size is nu(G). An isolated vertex has no incident edge, so a graph containing one has no edge cover under the standard definition.
The rule is simple: vertex covers use vertices to cover edges; line covers use edges to cover vertices; independent sets prohibit adjacent vertices; matchings prohibit incident edges. These graph-covering definitions and identities are part of GATE CS exam preparation. For wider path, cycle, colouring and degree vocabulary, use Graph Theory for GATE CS: Euler, Coloring, Worked Formulas.
2. Vertex cover worked example on the six-vertex path P6
Use the path 1-2-3-4-5-6, with V={1,2,3,4,5,6} and E={12,23,34,45,56}. Take C={2,4,6}. Edge 12 meets 2, 23 meets 2, 34 meets 4, 45 meets 4, and 56 meets 6. Therefore C is a vertex cover of size 3.
Now prove that it is minimum. Edges 12, 34 and 56 form a matching of size 3. Their endpoints are pairwise disjoint, so one selected vertex cannot cover two of these three edges. Every vertex cover therefore needs at least three vertices. Since C uses exactly three, tau(P6)=3.
Its complement is I=V-C={1,3,5}. None of 13, 15 or 35 belongs to the path's edge set, so I is independent and has size 3.

3. Vertex covers and independent sets are complements
If C covers every edge, two vertices outside C cannot be adjacent, so V-C is independent. Conversely, if I is independent, no edge has both endpoints in I. Every edge therefore meets V-I, making V-I a vertex cover.
Thus alpha(G)+tau(G)=|V| for every finite graph. Here alpha(P6)=6-tau(P6)=6-3=3. The witness {1,3,5} has complement {2,4,6}, a minimum vertex cover.
The optimum need not be unique. C'={1,3,5} is also a minimum vertex cover, and V-C'={2,4,6} is a maximum independent set. The invariant values remain tau=3 and alpha=3.
4. Line covering comes from maximum matching
The maximum matching M={12,34,56} touches all six vertices, so it is an edge cover and rho(P6)<=3. Two edges touch at most four vertices, so rho(P6)>=3. Therefore rho(P6)=3.
For any graph with no isolated vertices,
rho(G)=|V|-nu(G).
Start with a maximum matching of nu edges, covering 2nu vertices. Add one incident edge for each of the other |V|-2nu vertices. The total is nu+(|V|-2nu)=|V|-nu. For P6, rho=6-3=3.
The condition matters. Let H have V(H)={1,2,3,4} and E(H)={12,23}. Vertex 4 is isolated, so no line cover exists. The vertex cover {2} is nevertheless valid and minimum.
5. Minimal vs minimum, maximal vs maximum on the same graph
Minimum and maximum compare size with every feasible set. Minimal means no chosen element can be removed while preserving feasibility. Maximal means none can be added. Every minimum cover is minimal, and every maximum independent set is maximal, but the converses can fail.
In P6, J={2,5} is independent because 25 is not an edge. It is maximal because 1 and 3 meet 2, while 4 and 6 meet 5. But |J|=2<3=alpha(P6), so it is not maximum.
Its complement is D=V-J={1,3,4,6}. This is a minimal vertex cover. Removing 1, 3, 4 or 6 leaves edge 12, 23, 45 or 56 uncovered, respectively. Yet |D|=4>3=tau(P6), so it is not minimum. Complements pair maximal independent sets with minimal vertex covers, and maximum independent sets with minimum vertex covers.
The line-cover counterpart is F={12,23,45,56}. It covers every vertex. Deleting 12, 23, 45 or 56 leaves vertex 1, 3, 4 or 6 uncovered, respectively. Thus F is minimal, but |F|=4>3=rho(P6), so it is not minimum.

6. Covering numbers on standard graphs and theorem shortcuts
Graph |
|
|
|
| Exact witness |
|---|---|---|---|---|---|
| 3 | 3 | 3 | 3 | Cover |
| 2 | 2 | 2 | 2 | Cover |
| 2 | 1 | 1 | 2 | Cover |
| 1 | 3 | 1 | 3 | Cover |
Two checks govern every row: alpha+tau=|V| always, while rho+nu=|V| requires no isolated vertices. For the four-vertex star, these give 3+1=4 and 3+1=4.
Konig's theorem gives another shortcut: in a bipartite graph, tau=nu. It applies to P6, C4 and K1,3. It does not apply to the non-bipartite graph K3, where tau=2 but nu=1. Always establish bipartiteness before using it.
7. Representative graph-covering question patterns and common traps
Representative CS exam-style tasks ask you to identify sets, distinguish inclusion-minimal from smallest-cardinality, derive one covering number from another, construct a cover from a matching, or detect an isolated vertex.
Mistake | Why it fails | Exact repair |
|---|---|---|
Swapping line and vertex covers | The selected object is wrong | Vertex cover selects vertices; line cover selects edges |
Reading minimal as minimum | Local irreducibility does not prove smallest size | Compare cardinality or prove a lower bound |
Reading maximal as maximum | Inability to add does not prove largest size | Produce an upper bound or a larger witness |
Applying | No edge can cover the isolated vertex | Check every vertex has positive degree first |
Assuming a maximum matching is always an edge cover | Unmatched vertices may remain | Add an incident edge for every unmatched vertex |
Using | The equality is scoped to bipartite graphs | Establish bipartiteness first |
Four rapid checks:
On
P6,{2,5}is maximal independent but not maximum: size 2 versusalpha=3.On
P6,{1,3,4,6}is minimal vertex cover but not minimum: size 4 versustau=3.If a graph with no isolates has
|V|=8andnu=3, thenrho=8-3=5. If it also hastau=3, thenalpha=8-3=5.For
Hwith edges{12,23}and isolated vertex4,{2}is a minimum vertex cover and{1,3,4}is a maximum independent set, but no edge cover exists.
The P6 derivations establish the covering identities. Apply them to planar bounds, forced cover vertices, the Petersen graph and smallest maximal sets in Graph Covering MCQs: 11 Solved Vertex Cover and Independent Set Questions. Once you can justify every untimed answer, use the GATE Test Series as the timed next step.
8. Graph covering: the short version and next step
A vertex cover covers edges.
A line cover covers vertices.
The complement of a vertex cover is independent.
alpha+tau=|V|.For a graph with no isolates,
rho+nu=|V|.Minimal or maximal means locally irreducible; minimum or maximum means globally optimal in cardinality.
Redraw P6 from E={12,23,34,45,56} without looking. Reproduce the minimum vertex cover {2,4,6}, maximum independent set {1,3,5}, minimum line cover {12,34,56}, and maximal non-maximum independent set {2,5}. Then explain why {1,3,4,6} and {12,23,45,56} are minimal but not minimum.
For a sequenced GATE CS route through the broader discrete-mathematics plan, continue with GATE Guidance by Sanchit Sir.
Keep learning
Graph Covering MCQs: 11 Solved Vertex Cover and Independent Set Questions
Solve 11 graph-covering questions and learn the reusable moves behind vertex covers, independent sets, edge covers, spanning trees, and minimal versus minimum sets.
Graph Matching: Maximal, Maximum and Perfect Matchings with Augmenting-Path Examples
Learn how maximal, maximum and perfect matchings differ. Follow one bipartite graph from a stuck greedy choice to a perfect matching using two augmenting paths.
Planar Graphs and Euler's Formula for GATE: Planarity Checks, Matching and Vertex Covers Solved
Use Euler's formula and the correct planar edge bound on K4, K5 and K3,3. Then connect maximum matching to minimum vertex cover in a solved bipartite graph.
Minimum and Maximum Degree MCQs: 11 Solved Degree Constraints and Havel-Hakimi Questions
Solve 11 degree-constraint questions with parity checks, edge bounds, constructions and complete Havel-Hakimi certificates. Each explanation shows the shortest reliable route.





