isNClique_map_iff — Mathlib

English

There exists a 3-clique in G if and only if there exists a closed walk of length 3 in G.

Русский

Существует 3-клик в графе G тогда и только тогда, когда существует замкнутая прогулка длины 3 в G.

LaTeX

$$$$\\exists s:\\ Finset\\ α,\\ G.IsNClique 3 s \\iff \\exists u:\\, \\exists w:\\, (u,w)\\text{ с } w IsCycle \\land w.length = 3$$$$

Lean4

theorem isNClique_map_iff (hn : 1 < n) {t : Finset β} {f : α ↪ β} :
    (G.map f).IsNClique n t ↔ ∃ s : Finset α, G.IsNClique n s ∧ s.map f = t :=
  by
  rw [isNClique_iff, isClique_map_finset_iff, or_and_right, or_iff_right (by rintro ⟨h', rfl⟩; exact h'.not_gt hn)]
  constructor
  · rintro ⟨⟨s, hs, rfl⟩, rfl⟩
    simp [isNClique_iff, hs]
  rintro ⟨s, hs, rfl⟩
  simp [hs.card_eq, hs.isClique]

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