Dashboard/Block 3: Covers & Matchings/Week 7
Week 7Covers & Matchings

Covers, Independent Sets & Kruskal

We introduce the four fundamental graph parameters: vertex cover τ(G)\tau(G), matching number ν(G)\nu(G), independence number α(G)\alpha(G), and edge cover ρ(G)\rho(G). Gallai's theorems connect these. We also learn Kruskal's algorithm for minimum spanning trees.

Learning Objectives

Define τ, ν, α, ρ and understand their relationships
State and prove Gallai's theorems
Apply Kruskal's algorithm to find minimum spanning trees
Use the complement relationship between covers and independent sets

Key Concepts

Covers & Independent Sets

A vertex cover is a set S⊆VS \subseteq V such that every edge has at least one endpoint in SS. An independent set is a set with no edges between its vertices. An edge cover is a set of edges covering all vertices.

These are complementary: SS is a vertex cover   ⟺  \iff V∖SV \setminus S is an independent set.

  • -

    SS is a vertex cover   ⟺  \iff V∖SV \setminus S is an independent set

  • -

    α(G)+τ(G)=n\alpha(G) + \tau(G) = n (complement relationship)

  • -

    ν(G)≤τ(G)\nu(G) \leq \tau(G) (every cover must include at least one endpoint of each matching edge)

  • -

    α(G)≤ρ(G)\alpha(G) \leq \rho(G) (each independent vertex needs a distinct covering edge)

  • -

    For bipartite graphs: ν(G)=τ(G)\nu(G) = \tau(G) (König's theorem — covered in Week 9)

Gallai's Theorems

Gallai proved two fundamental identities connecting these parameters:

  • -

    First identity: α+τ=n\alpha + \tau = n (vertex cover ↔ independent set complement)

  • -

    Second identity: ν+ρ=n\nu + \rho = n (requires no isolated vertices)

  • -

    These relate maximum and minimum parameters in a beautiful way

Kruskal's Algorithm

Kruskal's algorithm finds a minimum spanning tree (MST) of a weighted connected graph. It greedily adds edges in order of increasing weight, skipping any edge that would create a cycle.

  • -

    Sort edges by weight, add each unless it creates a cycle

  • -

    Uses Union-Find data structure for efficient cycle detection

  • -

    Time complexity: O(mlog⁡m)O(m \log m) (dominated by sorting)

  • -

    Produces an MST by the greedy property (cut property)

W6: Planarity & Euler's FormulaW8: Matchings & Hall's Theorem