bipartite_cycle_length_le
In any bipartite graph with vertex parts V and W, every simple cycle has length at most 2 * min(|V|, |W|).
Statement
theorem bipartite_cycle_length_le {V W : Type*} [Fintype V] [Fintype W] (G : SimpleGraph (V ⊕ W)) (hG : G ≤ completeBipartiteGraph V W) {u : V ⊕ W} (p : G.Walk u u) (hp : p.IsCycle) : p.length ≤ 2 * min (Fintype.card V) (Fintype.card W)
- Source
- folklore
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any finite types $V$ and $W$, let $G$ be a simple graph on the disjoint union $V \oplus W$ that is a subgraph of the complete bipartite graph completeBipartiteGraph V W (that is, $G \le \text{completeBipartiteGraph } V\ W$). For any vertex $u \in V \oplus W$ and any closed walk $p$ in $G$ from $u$ to $u$, if $p$ is a cycle (p.IsCycle), then the length of $p$ is at most $2 \min(|V|, |W|)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
In a bipartite graph with parts V and W, every simple cycle alternates between V and W at every step. Because the cycle is closed, it visits vertices in V and W in equal numbers, meaning that the cycle length n satisfies n = 2 * |V ∩ cycle| = 2 * |W ∩ cycle|. Since all vertices of a simple cycle are distinct, the vertices in V form a subset of V (so |V ∩ cycle| ≤ |V|) and those in W form a subset of W (so |W ∩ cycle| ≤ |W|), which immediately bounds the cycle length by 2 * min(|V|, |W|).
Adjacent vertices in a bipartite graph lie on opposite sides of the bipartition.
Since G is a subgraph of the complete bipartite graph between V and W, any edge in G must connect a vertex in V to a vertex in W or vice versa, so the two endpoints cannot have the same side indicator.
uses
completeBipartiteGraphhave := hG h cases a <;> cases c <;> simp_all [completeBipartiteGraph]
Shifting the index of an indicator sum along {0, ..., m - 1} changes the total by the boundary difference b(m) - b(0). automation
By induction on m: the base case m = 0 holds immediately, and the induction step splits off the last term of the sum using Finset.sum_range_succ, after which linear arithmetic (omega) closes the equation.
uses
Finset.sum_range_succinduction m with | zero => simp | succ m ih => rw [Finset.sum_range_succ, Finset.sum_range_succ] omega
Summing an alternating boolean sequence and its shift over {0, ..., n - 1} gives n.
Because b(i) ≠ b(i + 1) for all i < n, exactly one of b(i) and b(i + 1) is true for each step, so their indicators sum to 1. Combining the two sums into a single sum of 1 over n indices yields n.
uses
Finset.sum_add_distrib,Finset.mem_range.mp,Finset.sum_congr,Finset.sum_const,Finset.card_range,smul_eq_mul,mul_onerw [← Finset.sum_add_distrib] have h : ∀ i ∈ Finset.range n, (if b i then 1 else 0) + (if b (i + 1) then 1 else 0) = 1 := by intro i hi have hne := halt i (Finset.mem_range.mp hi) cases h1 : b i <;> cases h2 : b (i + 1) · rw [h1, h2] at hne; contradiction · simp · simp · rw [h1, h2] at hne; contradiction rw [Finset.sum_congr rfl h, Finset.sum_const, Finset.card_range, smul_eq_mul, mul_one]
For an alternating periodic boolean sequence of length n with b(n) = b(0), the length is twice the number of true values: n = 2 * ∑_{i < n} [b(i)]. automation
Since b(n) = b(0), the shift identity implies ∑_{i < n} [b(i + 1)] = ∑_{i < n} [b(i)]. Combining this with the alternating sum identity that adds them to n gives n = 2 * ∑_{i < n} [b(i)], solved by linear arithmetic (omega).
uses
bipartite_cycle_length_le_bool_shift_sum,bipartite_cycle_length_le_bool_sum_althave h1 := bipartite_cycle_length_le_bool_shift_sum n b have h2 := bipartite_cycle_length_le_bool_sum_alt n b halt rw [hcyc] at h1 omega
Any finite set of vertices all belonging to V has cardinality at most |V|.
Every vertex in T has isLeft = true, so T is a subset of the image of V under the natural embedding Sum.inl. Because Sum.inl is injective, the cardinality of T is bounded by the cardinality of V.
uses
Finset.mem_image.mpr,Finset.mem_univ,Finset.card_le_card,Finset.card_image_of_injective,Sum.inl_injective,Finset.card_univclassical have hsub : T ⊆ Finset.image Sum.inl (Finset.univ : Finset V) := by intro x hx have hx' := hT x hx cases x with | inl v => exact Finset.mem_image.mpr ⟨v, Finset.mem_univ v, rfl⟩ | inr w => simp at hx' have hcard := Finset.card_le_card hsub rw [Finset.card_image_of_injective _ Sum.inl_injective, Finset.card_univ] at hcard exact hcard
Any finite set of vertices all belonging to W has cardinality at most |W|.
Every vertex in T has isRight = true, so T is a subset of the image of W under the natural embedding Sum.inr. Because Sum.inr is injective, the cardinality of T is bounded by the cardinality of W.
uses
Finset.mem_image.mpr,Finset.mem_univ,Finset.card_le_card,Finset.card_image_of_injective,Sum.inr_injective,Finset.card_univclassical have hsub : T ⊆ Finset.image Sum.inr (Finset.univ : Finset W) := by intro x hx have hx' := hT x hx cases x with | inl v => simp at hx' | inr w => exact Finset.mem_image.mpr ⟨w, Finset.mem_univ w, rfl⟩ have hcard := Finset.card_le_card hsub rw [Finset.card_image_of_injective _ Sum.inr_injective, Finset.card_univ] at hcard exact hcard
An element of V ⊕ W that is not on the left must be on the right.
A value of sum type V ⊕ W has only two constructors, Sum.inl and Sum.inr; having isLeft = false forces it to be Sum.inr, for which isRight is true.
cases x with | inl _ => simp at h | inr _ => rfl
The length of the cycle is twice the number of its vertices that lie in V.
Let b(i) indicate whether the i-th vertex of the cycle walk lies in V. Because edges in a bipartite graph alternate between shores, b(i) alternates at each step. Since the cycle is closed, b(p.length) = b(0). Thus, the alternating periodic sum identity implies p.length = 2 * ∑_{i < p.length} [b(i)].
uses
bipartite_cycle_length_le_side_ne,bipartite_cycle_length_le_bool_sumclassical let b : ℕ → Bool := fun i => (p.getVert i).isLeft have halt : ∀ i < p.length, b i ≠ b (i + 1) := fun i hi => bipartite_cycle_length_le_side_ne G hG (p.adj_getVert_succ hi) have hcyc : b p.length = b 0 := by simp [b, p.getVert_length, p.getVert_zero] have hlen : p.length = 2 * ∑ i ∈ Finset.range p.length, if b i then 1 else 0 := bipartite_cycle_length_le_bool_sum p.length b hcyc halt
The cycle vertex mapping is injective on the index set SF of V-vertices and on SG of W-vertices.
We define SF and SG as the sets of indices i < p.length where b(i) is true and false, respectively. Since p is a simple cycle, its vertex map is injective on {0, ..., p.length - 1}, and therefore injective when restricted to each subset SF and SG.
uses
Finset.mem_range.mp,Finset.mem_filter.mp,Nat.le_sub_one_of_lt,Finset.mem_coe.mplet SF := (Finset.range p.length).filter (fun i => b i = true) let SG := (Finset.range p.length).filter (fun i => b i = false) have hSF_range : ∀ i ∈ SF, i < p.length := fun i hi => Finset.mem_range.mp (Finset.mem_filter.mp hi).1 have hSG_range : ∀ i ∈ SG, i < p.length := fun i hi => Finset.mem_range.mp (Finset.mem_filter.mp hi).1 have hinjV : Set.InjOn p.getVert ↑SF := by intro i hi j hj hij have hi' : i ≤ p.length - 1 := Nat.le_sub_one_of_lt (hSF_range i (Finset.mem_coe.mp hi)) have hj' : j ≤ p.length - 1 := Nat.le_sub_one_of_lt (hSF_range j (Finset.mem_coe.mp hj)) exact hp.getVert_injOn' hi' hj' hij have hinjW : Set.InjOn p.getVert ↑SG := by intro i hi j hj hij have hi' : i ≤ p.length - 1 := Nat.le_sub_one_of_lt (hSG_range i (Finset.mem_coe.mp hi)) have hj' : j ≤ p.length - 1 := Nat.le_sub_one_of_lt (hSG_range j (Finset.mem_coe.mp hj)) exact hp.getVert_injOn' hi' hj' hij
The cardinalities of SF and SG equal the indicator sums for V and W, respectively.
By the definition of Finset.card_filter, the cardinality of a filtered set is the sum of the indicators of the filter predicate over the range.
uses
Finset.card_filter,Finset.sum_congrhave hSF_card : SF.card = ∑ i ∈ Finset.range p.length, if b i then 1 else 0 := by rw [Finset.card_filter] have hSG_card : SG.card = ∑ i ∈ Finset.range p.length, if ¬b i then 1 else 0 := by rw [Finset.card_filter] apply Finset.sum_congr rfl intro i _ cases b i <;> rfl
The number of cycle vertices in V is at most |V|.
Because the vertex map is injective on SF, the image of SF has cardinality |SF|. All vertices in this image lie in V, so by the earlier cardinality lemma, |SF| ≤ |V|.
uses
Finset.card_image_of_injOn,bipartite_cycle_length_le_card_le_card_V,Finset.mem_image.mp,Finset.mem_filter.mphave hV : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) ≤ Fintype.card V := by rw [← hSF_card, ← Finset.card_image_of_injOn hinjV] apply bipartite_cycle_length_le_card_le_card_V intro x hx obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hx exact (Finset.mem_filter.mp hi).2
The number of cycle vertices in V is also at most |W|.
The sum of the sizes of SF and SG equals p.length. Since p.length = 2 * |SF|, we have |SF| = |SG|. Since the vertex map is injective on SG and every vertex in its image has isLeft = false (hence isRight = true), the image has cardinality |SG| ≤ |W|, proving |SF| ≤ |W|.
uses
Finset.sum_add_distrib,Finset.sum_congr,Finset.sum_const,Finset.card_range,smul_eq_mul,mul_one,Finset.card_image_of_injOn,bipartite_cycle_length_le_card_le_card_W,Finset.mem_image.mp,bipartite_cycle_length_le_isRight_eq_true_of_isLeft_eq_false,Finset.mem_filter.mphave hW : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) ≤ Fintype.card W := by have hsum : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) + (∑ i ∈ Finset.range p.length, if ¬b i then 1 else 0) = p.length := by rw [← Finset.sum_add_distrib] have : ∀ i ∈ Finset.range p.length, (if b i then 1 else 0) + (if ¬b i then 1 else 0) = 1 := by intro i _ cases b i <;> rfl rw [Finset.sum_congr rfl this, Finset.sum_const, Finset.card_range, smul_eq_mul, mul_one] have hSG_le : SG.card ≤ Fintype.card W := by rw [← Finset.card_image_of_injOn hinjW] apply bipartite_cycle_length_le_card_le_card_W intro x hx obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hx exact bipartite_cycle_length_le_isRight_eq_true_of_isLeft_eq_false (p.getVert i) ((Finset.mem_filter.mp hi).2) have : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) = (∑ i ∈ Finset.range p.length, if ¬b i then 1 else 0) := by omega rw [this, ← hSG_card] exact hSG_le
The cycle length is at most 2 * min(|V|, |W|).
Since |SF| ≤ |V| and |SF| ≤ |W|, we have |SF| ≤ min(|V|, |W|). Multiplying both sides of this inequality by 2 and substituting p.length = 2 * |SF| yields p.length ≤ 2 * min(|V|, |W|).
uses
le_min,Nat.mul_le_mul_leftrw [hlen] have hmin : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) ≤ min (Fintype.card V) (Fintype.card W) := le_min hV hW exact Nat.mul_le_mul_left 2 hmin
completeBipartiteGraph- The complete bipartite graph with vertex set V ⊕ W whose edges connect every vertex of V to every vertex of W.
Finset.sum_range_succ- Splitting off the last term in a sum over Finset.range (n + 1): ∑_{x < n+1} f(x) = (∑_{x < n} f(x)) + f(n).
Finset.sum_add_distrib- Distributing a sum over addition: ∑ (f(x) + g(x)) = ∑ f(x) + ∑ g(x).
Finset.mem_range.mp- An element i belongs to Finset.range n if and only if i < n.
Finset.sum_congr- If two finite sets are equal and two summands agree on every element, their sums are equal.
Finset.sum_const- Summing a constant value b over a finite set s yields |s| • b.
Finset.card_range- The cardinality of Finset.range n is n.
smul_eq_mul- Scalar multiplication of natural numbers agrees with standard multiplication.
mul_one- Multiplying any element by 1 leaves it unchanged.
bipartite_cycle_length_le_bool_shift_sum- For any boolean sequence b, the shifted sum ∑_{i < m} [b(i+1)] + [b(0)] equals the unshifted sum ∑_{i < m} [b(i)] + [b(m)].
bipartite_cycle_length_le_bool_sum_alt- For an alternating boolean sequence of length n, the sum of b(i) plus the sum of b(i+1) equals n.
Finset.mem_image.mpr- An element y belongs to the image f(s) if there exists x ∈ s with f(x) = y.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
Sum.inl_injective- The left injection Sum.inl is an injective function.
Finset.card_univ- The cardinality of Finset.univ for a finite type α is Fintype.card α.
Sum.inr_injective- The right injection Sum.inr is an injective function.
bipartite_cycle_length_le_side_ne- In any subgraph of the complete bipartite graph, adjacent vertices lie on different sides of the bipartition.
bipartite_cycle_length_le_bool_sum- If a boolean sequence alternates at every step and is periodic with b(n) = b(0), then n = 2 * ∑_{i < n} [b(i)].
Finset.mem_filter.mp- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies p.
Nat.le_sub_one_of_lt- If a < b for natural numbers, then a ≤ b - 1.
Finset.mem_coe.mp- Membership in the coerced set ↑s is equivalent to membership in the finset s.
Finset.card_filter- The cardinality of a filtered finset equals the sum over the finset of the indicator of the filtering predicate.
Finset.card_image_of_injOn- If a function is injective on a finite set s, the cardinality of its image f(s) equals the cardinality of s.
bipartite_cycle_length_le_card_le_card_V- Any finite subset of V ⊕ W consisting solely of left vertices has cardinality at most |V|.
Finset.mem_image.mp- If y belongs to f(s), then there is some x ∈ s such that f(x) = y.
bipartite_cycle_length_le_card_le_card_W- Any finite subset of V ⊕ W consisting solely of right vertices has cardinality at most |W|.
bipartite_cycle_length_le_isRight_eq_true_of_isLeft_eq_false- If an element of V ⊕ W is not on the left, it must be on the right.
le_min- If c ≤ a and c ≤ b, then c ≤ min(a, b).
Nat.mul_le_mul_left- If n ≤ m, then k * n ≤ k * m for natural numbers.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma bipartite_cycle_length_le_side_ne {V W : Type*} (G : SimpleGraph (V ⊕ W)) (hG : G ≤ completeBipartiteGraph V W) {a c : V ⊕ W} (h : G.Adj a c) : a.isLeft ≠ c.isLeft := by have := hG h cases a <;> cases c <;> simp_all [completeBipartiteGraph]lemma bipartite_cycle_length_le_bool_shift_sum (m : ℕ) (b : ℕ → Bool) : (∑ i ∈ Finset.range m, if b (i + 1) then 1 else 0) + (if b 0 then 1 else 0) = (∑ i ∈ Finset.range m, if b i then 1 else 0) + (if b m then 1 else 0) := by induction m with | zero => simp | succ m ih => rw [Finset.sum_range_succ, Finset.sum_range_succ] omegalemma bipartite_cycle_length_le_bool_sum_alt (n : ℕ) (b : ℕ → Bool) (halt : ∀ i < n, b i ≠ b (i + 1)) : (∑ i ∈ Finset.range n, if b i then 1 else 0) + (∑ i ∈ Finset.range n, if b (i + 1) then 1 else 0) = n := by rw [← Finset.sum_add_distrib] have h : ∀ i ∈ Finset.range n, (if b i then 1 else 0) + (if b (i + 1) then 1 else 0) = 1 := by intro i hi have hne := halt i (Finset.mem_range.mp hi) cases h1 : b i <;> cases h2 : b (i + 1) · rw [h1, h2] at hne; contradiction · simp · simp · rw [h1, h2] at hne; contradiction rw [Finset.sum_congr rfl h, Finset.sum_const, Finset.card_range, smul_eq_mul, mul_one]lemma bipartite_cycle_length_le_bool_sum (n : ℕ) (b : ℕ → Bool) (hcyc : b n = b 0) (halt : ∀ i < n, b i ≠ b (i + 1)) : n = 2 * ∑ i ∈ Finset.range n, if b i then 1 else 0 := by have h1 := bipartite_cycle_length_le_bool_shift_sum n b have h2 := bipartite_cycle_length_le_bool_sum_alt n b halt rw [hcyc] at h1 omegalemma bipartite_cycle_length_le_card_le_card_V {V W : Type*} [Fintype V] (T : Finset (V ⊕ W)) (hT : ∀ x ∈ T, x.isLeft = true) : T.card ≤ Fintype.card V := by classical have hsub : T ⊆ Finset.image Sum.inl (Finset.univ : Finset V) := by intro x hx have hx' := hT x hx cases x with | inl v => exact Finset.mem_image.mpr ⟨v, Finset.mem_univ v, rfl⟩ | inr w => simp at hx' have hcard := Finset.card_le_card hsub rw [Finset.card_image_of_injective _ Sum.inl_injective, Finset.card_univ] at hcard exact hcardlemma bipartite_cycle_length_le_card_le_card_W {V W : Type*} [Fintype W] (T : Finset (V ⊕ W)) (hT : ∀ x ∈ T, x.isRight = true) : T.card ≤ Fintype.card W := by classical have hsub : T ⊆ Finset.image Sum.inr (Finset.univ : Finset W) := by intro x hx have hx' := hT x hx cases x with | inl v => simp at hx' | inr w => exact Finset.mem_image.mpr ⟨w, Finset.mem_univ w, rfl⟩ have hcard := Finset.card_le_card hsub rw [Finset.card_image_of_injective _ Sum.inr_injective, Finset.card_univ] at hcard exact hcardlemma bipartite_cycle_length_le_isRight_eq_true_of_isLeft_eq_false {V W : Type*} (x : V ⊕ W) (h : x.isLeft = false) : x.isRight = true := by cases x with | inl _ => simp at h | inr _ => rfl/-- Any simple cycle in a bipartite graph has length at most twice the size of the smaller shore. -/theorem bipartite_cycle_length_le {V W : Type*} [Fintype V] [Fintype W] (G : SimpleGraph (V ⊕ W)) (hG : G ≤ completeBipartiteGraph V W) {u : V ⊕ W} (p : G.Walk u u) (hp : p.IsCycle) : p.length ≤ 2 * min (Fintype.card V) (Fintype.card W) := by classical let b : ℕ → Bool := fun i => (p.getVert i).isLeft have halt : ∀ i < p.length, b i ≠ b (i + 1) := fun i hi => bipartite_cycle_length_le_side_ne G hG (p.adj_getVert_succ hi) have hcyc : b p.length = b 0 := by simp [b, p.getVert_length, p.getVert_zero] have hlen : p.length = 2 * ∑ i ∈ Finset.range p.length, if b i then 1 else 0 := bipartite_cycle_length_le_bool_sum p.length b hcyc halt let SF := (Finset.range p.length).filter (fun i => b i = true) let SG := (Finset.range p.length).filter (fun i => b i = false) have hSF_range : ∀ i ∈ SF, i < p.length := fun i hi => Finset.mem_range.mp (Finset.mem_filter.mp hi).1 have hSG_range : ∀ i ∈ SG, i < p.length := fun i hi => Finset.mem_range.mp (Finset.mem_filter.mp hi).1 have hinjV : Set.InjOn p.getVert ↑SF := by intro i hi j hj hij have hi' : i ≤ p.length - 1 := Nat.le_sub_one_of_lt (hSF_range i (Finset.mem_coe.mp hi)) have hj' : j ≤ p.length - 1 := Nat.le_sub_one_of_lt (hSF_range j (Finset.mem_coe.mp hj)) exact hp.getVert_injOn' hi' hj' hij have hinjW : Set.InjOn p.getVert ↑SG := by intro i hi j hj hij have hi' : i ≤ p.length - 1 := Nat.le_sub_one_of_lt (hSG_range i (Finset.mem_coe.mp hi)) have hj' : j ≤ p.length - 1 := Nat.le_sub_one_of_lt (hSG_range j (Finset.mem_coe.mp hj)) exact hp.getVert_injOn' hi' hj' hij have hSF_card : SF.card = ∑ i ∈ Finset.range p.length, if b i then 1 else 0 := by rw [Finset.card_filter] have hSG_card : SG.card = ∑ i ∈ Finset.range p.length, if ¬b i then 1 else 0 := by rw [Finset.card_filter] apply Finset.sum_congr rfl intro i _ cases b i <;> rfl have hV : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) ≤ Fintype.card V := by rw [← hSF_card, ← Finset.card_image_of_injOn hinjV] apply bipartite_cycle_length_le_card_le_card_V intro x hx obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hx exact (Finset.mem_filter.mp hi).2 have hW : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) ≤ Fintype.card W := by have hsum : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) + (∑ i ∈ Finset.range p.length, if ¬b i then 1 else 0) = p.length := by rw [← Finset.sum_add_distrib] have : ∀ i ∈ Finset.range p.length, (if b i then 1 else 0) + (if ¬b i then 1 else 0) = 1 := by intro i _ cases b i <;> rfl rw [Finset.sum_congr rfl this, Finset.sum_const, Finset.card_range, smul_eq_mul, mul_one] have hSG_le : SG.card ≤ Fintype.card W := by rw [← Finset.card_image_of_injOn hinjW] apply bipartite_cycle_length_le_card_le_card_W intro x hx obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hx exact bipartite_cycle_length_le_isRight_eq_true_of_isLeft_eq_false (p.getVert i) ((Finset.mem_filter.mp hi).2) have : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) = (∑ i ∈ Finset.range p.length, if ¬b i then 1 else 0) := by omega rw [this, ← hSG_card] exact hSG_le rw [hlen] have hmin : (∑ i ∈ Finset.range p.length, if b i then 1 else 0) ≤ min (Fintype.card V) (Fintype.card W) := le_min hV hW exact Nat.mul_le_mul_left 2 hmin