HLPL / VerTeX Modelling Language Documentation

← lessons

Maximum matching and König's theorem

The most edges sharing no vertex — and why it equals the cover.

Chapter: XIIb — Graph theory · lesson id gt-matching · practice lesson

---

A $matching$ picks edges instead of vertices: as many edges as possible so that no vertex is used twice — think of pairing people off, where nobody can be in two pairs.

One binary variable x_e per edge (1 = in the matching). One constraint per vertex: the edges incident to it sum to at most 1. Maximise the number of edges.

On our graph the answer is 2 — for example {13, 45}. Vertices 3 and 6 are leaves that both compete for a hub, so no perfect (three-edge) pairing exists.

Now the punchline. Maximum matching = 2, and minimum vertex cover = 2 (lesson 2). That is no accident: König's theorem says that in any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. Our graph is bipartite, so the two numbers must agree.

Predict before running

Same graph. What is the largest set of edges you can pick so that no two of them share a vertex?

• 2 — e.g. {1-3, 4-5}
• 3 — a perfect matching pairing all six vertices
• 1 — any two edges must touch

Starter code

model match
set E = {12, 13, 14, 25, 45, 56}
bin x, forall e in E
# TODO: one constraint per vertex — its incident edges sum to <= 1
#   v1: 12,13,14   v2: 12,25   v3: 13   v4: 14,45   v5: 25,45,56   v6: 56
max sum_{e in E}{x_{e}}
end

import elytica
def main():
  elytica.init_model("match")
  elytica.run_model("match")
  for i in [12,13,14,25,45,56]:
    print("x"+str(i), "=", elytica.get_variable_value("match", "x"+str(i)))
  print("obj =", elytica.get_best_primal_bound("match"))
  return 0

Hint

One constraint per vertex: sum of its incident edge-variables <= 1. Leaves 3 and 6 both need a hub, capping the matching at 2.

What counts as correct

• no-error — Model solves
• numeric-match — Maximum matching has 2 edges — equal to the minimum vertex cover (König)
• code-contains — Reads the objective from the solver (no hardcoding)

Solution

model match
set E = {12, 13, 14, 25, 45, 56}
bin x, forall e in E
constr x_{12} + x_{13} + x_{14} <= 1
constr x_{12} + x_{25} <= 1
constr x_{13} <= 1
constr x_{14} + x_{45} <= 1
constr x_{25} + x_{45} + x_{56} <= 1
constr x_{56} <= 1
max sum_{e in E}{x_{e}}
end

import elytica
def main():
  elytica.init_model("match")
  elytica.run_model("match")
  for i in [12,13,14,25,45,56]:
    print("x"+str(i), "=", elytica.get_variable_value("match", "x"+str(i)))
  print("obj =", elytica.get_best_primal_bound("match"))
  return 0

Mastery variant

A plain path 1-2-3-4-5-6. How many disjoint edges fit on a six-vertex path?

model match_v
# path: 1-2-3-4-5-6
set E = {12, 23, 34, 45, 56}
bin x, forall e in E
# TODO: one <= 1 constraint per vertex
max sum_{e in E}{x_{e}}
end

import elytica
def main():
  elytica.init_model("match_v")
  elytica.run_model("match_v")
  for i in [12,23,34,45,56]:
    print("x"+str(i), "=", elytica.get_variable_value("match_v", "x"+str(i)))
  print("obj =", elytica.get_best_primal_bound("match_v"))
  return 0

Read this through MCP: read with path: "lessons/gt-matching", or resource hlpl://lessons/gt-matching.