girth_anti

Mathlib.Combinatorics.SimpleGraph.Girth

URI: https://scilib.ai/kg/mathlib#SimpleGraph.girth_anti

← MathLib Explorer

English

If G ≤ G' and G is not acyclic, then the girth of G' is at most the girth of G.

Русский

Если G ⊆ G' и G не ацикличен, то гирит(G') ≤ гирит(G).

LaTeX

$$$$G \le G' \Rightarrow \mathrm{girth}(G') \le \mathrm{girth}(G).$$$$

Lean4

theorem girth_anti {G' : SimpleGraph α} (hab : G ≤ G') (h : ¬G.IsAcyclic) : G'.girth ≤ G.girth :=
  ENat.toNat_le_toNat (egirth_anti hab) <| egirth_eq_top.not.mpr h

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

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

Разделы

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

Аффилиация

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