AFTD Auto-Formalizing Theoretical Domains

bipartite_cycle_length_le

theoremverified

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|).

  1. 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.

    lines 4–5

    uses completeBipartiteGraph

      have := hG h
      cases a <;> cases c <;> simp_all [completeBipartiteGraph]
  2. 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.

    lines 10–14

    uses Finset.sum_range_succ

      induction m with
      | zero => simp
      | succ m ih =>
        rw [Finset.sum_range_succ, Finset.sum_range_succ]
        omega
  3. 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.

    lines 18–27

    uses Finset.sum_add_distrib, Finset.mem_range.mp, Finset.sum_congr, Finset.sum_const, Finset.card_range, smul_eq_mul, mul_one

      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]
  4. 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).

    lines 32–35

    uses bipartite_cycle_length_le_bool_shift_sum, bipartite_cycle_length_le_bool_sum_alt

      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
      omega
  5. 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.

    lines 39–50

    uses Finset.mem_image.mpr, Finset.mem_univ, Finset.card_le_card, Finset.card_image_of_injective, Sum.inl_injective, Finset.card_univ

      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 hcard
  6. 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.

    lines 54–65

    uses Finset.mem_image.mpr, Finset.mem_univ, Finset.card_le_card, Finset.card_image_of_injective, Sum.inr_injective, Finset.card_univ

      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 hcard
  7. 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.

    lines 69–71

      cases x with
      | inl _ => simp at h
      | inr _ => rfl
  8. 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)].

    lines 78–85

    uses bipartite_cycle_length_le_side_ne, bipartite_cycle_length_le_bool_sum

      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
  9. 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.

    lines 86–99

    uses Finset.mem_range.mp, Finset.mem_filter.mp, Nat.le_sub_one_of_lt, Finset.mem_coe.mp

      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
  10. 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.

    lines 100–106

    uses Finset.card_filter, Finset.sum_congr

      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
  11. 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|.

    lines 107–112

    uses Finset.card_image_of_injOn, bipartite_cycle_length_le_card_le_card_V, Finset.mem_image.mp, Finset.mem_filter.mp

      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
  12. 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|.

    lines 113–131

    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.mp

      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
  13. 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|).

    lines 132–135

    uses le_min, Nat.mul_le_mul_left

      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
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

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
See it in the graphDiscuss this resultChallenge it