Theorems · Theorem · combinatorics

SimpleGraph.IsTuranMaximal.not_adj_trans

∀ {V : Type u_1} [inst : Fintype V] {G : SimpleGraph V} [inst_1 : DecidableRel G.Adj] {r : ℕ} {s t u : V},
  G.IsTuranMaximal r → ¬G.Adj t s → ¬G.Adj s u → ¬G.Adj t u

In a Turán-maximal graph, non-adjacency is transitive.

Defined in

Mathlib.Combinatorics.SimpleGraph.Extremal.Turan

Cited by

1 results in Mathlib

Foundations

Depth 80 from the axioms · uses propext, Classical.choice, Quot.sound

Assumes

FintypeDecidableRel