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

Updated 3 Nov 20266 min read
Graph Covering: Line and Vertex Covers, Independent Sets, Minimal vs Minimum, Maximal vs Maximum

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.

Path graph P6 with cover C={2,4,6} shaded, independent set I={1,3,5} outlined, and matching M={12,34,56} drawn as double edges.

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.

Two panels on P6: maximal independent set {2,5} beside minimal vertex cover {1,3,4,6}, plus minimal edge cover {12,23,45,56}.

6. Covering numbers on standard graphs and theorem shortcuts

Graph

tau

alpha

nu

rho

Exact witness

P6

3

3

3

3

Cover {2,4,6}; independent {1,3,5}; matching and edge cover {12,34,56}

C4, edges {12,23,34,41}

2

2

2

2

Cover {1,3}; independent {2,4}; matching and edge cover {12,34}

K3, edges {12,23,31}

2

1

1

2

Cover {1,2}; independent {3}; matching {12}; edge cover {12,23}

K1,3, centre c, leaves {a,b,d}

1

3

1

3

Cover {c}; independent {a,b,d}; any one spoke is a maximum matching; all three spokes form the edge 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 rho=|V|-nu with an isolate

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 tau=nu without checking the graph

The equality is scoped to bipartite graphs

Establish bipartiteness first

Four rapid checks:

  1. On P6, {2,5} is maximal independent but not maximum: size 2 versus alpha=3.

  2. On P6, {1,3,4,6} is minimal vertex cover but not minimum: size 4 versus tau=3.

  3. If a graph with no isolates has |V|=8 and nu=3, then rho=8-3=5. If it also has tau=3, then alpha=8-3=5.

  4. For H with edges {12,23} and isolated vertex 4, {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.