mono

Mathlib.Combinatorics.SimpleGraph.Clique

URI: https://scilib.ai/kg/mathlib#SimpleGraph.CliqueFree.mono

← MathLib Explorer

English

If the vertex set cardinality is less than n, then G has no n-clique.

Русский

Если кардинал множества вершин меньше n, то у G нет n-клики.

LaTeX

$$$ G.CliqueFree(n) \text{ if } card(\alpha) < n. $$$

Lean4

theorem mono (h : m ≤ n) : G.CliqueFree m → G.CliqueFree n :=
  by
  intro hG s hs
  obtain ⟨t, hts, ht⟩ := exists_subset_card_eq (h.trans hs.card_eq.ge)
  exact hG _ ⟨hs.isClique.subset hts, ht⟩

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

Научная платформа российской исследовательской школы.

Разделы

MathLib Explorer
Graph RAG
Лаборатория
Блог
О проекте
Команда

Аффилиация

Вычислительный центр им. А. А. Дороницына при ФИЦ «Информатика и Управление» РАН frccsc.ru