AFTD Auto-Formalizing Theoretical Domains

op_1695_bipartite_graph_fortuin_kasteleyn

theoremverifiedformalization

For every bipartite simple graph G = (V, E), the bipartite subgraph polynomial bipartite_subgraph_magic_poly G equals 8^{-|V|} times the Fortuin-Kasteleyn polynomial fortuin_kasteleyn_poly G 8 (-2).

Statement

theorem op_1695_bipartite_graph_fortuin_kasteleyn {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) :
    bipartite_subgraph_magic_poly G = (1 / (8 ^ Fintype.card V : ℝ)) * fortuin_kasteleyn_poly G 8 (-2)
Formalizes
OP-1695
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • bipartite_subgraph_magic_polyFor a finite simple graph G = (V, E), the bipartite subgraph magic polynomial is 8^{-|V|} times the sum over all edge subsets A ⊆ E such…
  • fortuin_kasteleyn_polyFor a finite simple graph G = (V, E) and real parameters q, w, the Fortuin-Kasteleyn random-cluster polynomial Z_G(q, w) is the sum over…

Read back from the Lean

For any finite type $V$ with decidable equality, and any simple graph $G$ on $V$ with decidable adjacency, if $G$ is bipartite (G.IsBipartite), then the bipartite subgraph polynomial of $G$ (bipartite_subgraph_magic_poly G) is equal to $8^{-|V|}$ times the Fortuin–Kasteleyn polynomial of $G$ evaluated at parameters $q = 8$ and $w = -2$ ((1 / (8 ^ Fintype.card V : ℝ)) * fortuin_kasteleyn_poly G 8 (-2)).

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

Every subgraph of a bipartite graph is itself bipartite, as it inherits the 2-coloring of the parent graph. Expanding the definition of the bipartite subgraph magic polynomial reveals a sum over all edge subsets of an indicator for bipartiteness times the Fortuin-Kasteleyn summand (-2)^{|A|} 8^{c(A)}, scaled by 8^{-|V|}. Because G is bipartite, every edge subset induces a bipartite subgraph, so the indicator is always true and the sum identically matches the Fortuin-Kasteleyn polynomial Z_G(8, -2).

  1. The graph G admits a 2-coloring, and the edge set A is a subset of the edge set of G.

    Because G is bipartite, it admits a proper 2-coloring c : V → Fin 2. Furthermore, coercing the inclusion of finite edge sets A ⊆ G.edgeFinset shows that every edge in A belongs to the edge set of G.

    lines 6–9

    uses SimpleGraph.mem_edgeFinset.mp, Finset.mem_coe.mp

      obtain ⟨c⟩ := hG
      have hsub : (↑A : Set (Sym2 V)) ⊆ G.edgeSet := by
        intro e he
        exact SimpleGraph.mem_edgeFinset.mp (hA (Finset.mem_coe.mp he))
  2. The graph spanned by the edge set A is a subgraph of G.

    By SimpleGraph.fromEdgeSet_le, a graph generated from an edge set is a subgraph of G if and only if all of its non-loop edges belong to G. Since every edge in A is an edge of G, the edge-induced subgraph is a subgraph of G.

    lines 10–12

    uses SimpleGraph.fromEdgeSet_le

      have hle : SimpleGraph.fromEdgeSet (↑A : Set (Sym2 V)) ≤ G := by
        rw [SimpleGraph.fromEdgeSet_le]
        exact fun e he => hsub he.1
  3. The subgraph formed by the edge set A is bipartite.

    Vertices adjacent in the subgraph generated by A are also adjacent in G, so they receive distinct colors under the coloring c of G. Hence c provides a valid 2-coloring for the subgraph, showing it is bipartite.

    lines 13–15

      refine ⟨⟨c.toFun, ?_⟩⟩
      intro a b hadj
      exact c.map_rel' (hle hadj)
  4. It suffices to show that the sum over edge subsets in the bipartite subgraph magic polynomial equals that in the Fortuin-Kasteleyn polynomial Z_G(8, -2).

    Unfolding the definitions of bipartite_subgraph_magic_poly and fortuin_kasteleyn_poly reveals that both sides share the common prefactor 8^{-|V|}. Cancelling this prefactor reduces the identity to proving that the two sums over the powerset of edges are equal.

    lines 21–22

      rw [bipartite_subgraph_magic_poly, fortuin_kasteleyn_poly]
      congr 1
  5. The two sums are equal term-by-term because every edge-induced subgraph is bipartite.

    Comparing the sums term-by-term using Finset.sum_congr, each edge subset A ⊆ E(G) spans a bipartite subgraph by the helper lemma op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite. Thus if_pos simplifies the indicator condition to its positive branch, matching the summand (-2)^{|A|} 8^{c(A)} of the Fortuin-Kasteleyn polynomial.

    lines 23–25

    uses Finset.sum_congr, if_pos, op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite, Finset.mem_powerset.mp

      apply Finset.sum_congr rfl
      intro A hA
      rw [if_pos (op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite G hG A (Finset.mem_powerset.mp hA))]
SimpleGraph.mem_edgeFinset.mp
An edge of a graph belongs to its edge set if it belongs to its finite edge set.
Finset.mem_coe.mp
An element belongs to a finite set if it belongs to the set obtained by coercing that finite set.
SimpleGraph.fromEdgeSet_le
The simple graph formed by an edge set s is a subgraph of G if and only if every non-loop pair in s is an edge of G.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
if_pos
A conditional expression `if c then t else e` equals t whenever c is true.
op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite
Any simple graph formed by a subset of the edges of a bipartite graph is itself bipartite.
Finset.mem_powerset.mp
A finite set belongs to the powerset of s if and only if it is a subset of s.

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

private lemma op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite)    (A : Finset (Sym2 V)) (hA : A ⊆ G.edgeFinset) :    (SimpleGraph.fromEdgeSet (↑A : Set (Sym2 V))).IsBipartite := by  obtain ⟨c⟩ := hG  have hsub : (↑A : Set (Sym2 V)) ⊆ G.edgeSet := by    intro e he    exact SimpleGraph.mem_edgeFinset.mp (hA (Finset.mem_coe.mp he))  have hle : SimpleGraph.fromEdgeSet (↑A : Set (Sym2 V)) ≤ G := by    rw [SimpleGraph.fromEdgeSet_le]    exact fun e he => hsub he.1  refine ⟨⟨c.toFun, ?_⟩⟩  intro a b hadj  exact c.map_rel' (hle hadj)/-- For a bipartite graph, the bipartite subgraph magic polynomial equals 8^{-|V|} Z_G(8, -2). -/theorem op_1695_bipartite_graph_fortuin_kasteleyn {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.IsBipartite) :    bipartite_subgraph_magic_poly G = (1 / (8 ^ Fintype.card V : ℝ)) * fortuin_kasteleyn_poly G 8 (-2) := by  rw [bipartite_subgraph_magic_poly, fortuin_kasteleyn_poly]  congr 1  apply Finset.sum_congr rfl  intro A hA  rw [if_pos (op_1695_bipartite_graph_fortuin_kasteleyn_from_edge_set_is_bipartite G hG A (Finset.mem_powerset.mp hA))]
See it in the graphDiscuss this resultChallenge it