maximumIndepSet_exists — Mathlib

English

Correspondences between maximum indep sets and maximum cliques via complement yield simple equalities.

Русский

Соответствия между максимальными независимыми множествами и максимальными кликами через дополнение приводят к простым равенствам.

LaTeX

$$IsMaximumIndepSet and IsMaximumClique are dual via complement: isMaximumIndepSet(s) ⇔ isMaximumClique(s) on G^c$$

Lean4

theorem maximumIndepSet_exists [Fintype α] : ∃ (s : Finset α), G.IsMaximumIndepSet s := by
  simp [← isMaximumClique_compl, maximumClique_exists]

Похожие утверждения