AFTD Auto-Formalizing Theoretical Domains

bipartite_subgraph_magic_poly

def

For 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 that (V, A) is bipartite of (-2)^{|A|} 8^{k(V,A)}, where k(V,A) is the number of connected components of the spanning subgraph (V, A).

Statement

open scoped Classical in
noncomputable def bipartite_subgraph_magic_poly {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : ℝ
Defined in
OP-1695
Verified
14 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given a finite type $V$ with decidable equality and a simple graph $G$ on $V$ with decidable adjacency, bipartite_subgraph_magic_poly G is the real number defined by: $$\frac{1}{8^{|V|}} \sum_{A \subseteq E(G)} \begin{cases} (-2)^{|A|} \cdot 8^{c(V, A)} & \text{if the spanning subgraph } (V, A) \text{ is bipartite} \\ 0 & \text{otherwise} \end{cases}$$ where: - $|V|$ is the number of vertices (Fintype.card V), - $E(G)$ is the finite edge set of $G$ (G.edgeFinset), - the sum is taken over all subsets $A \subseteq E(G)$ (G.edgeFinset.powerset), - $(V, A)$ is the spanning subgraph of $V$ with edge set $A$ (SimpleGraph.fromEdgeSet (A : Set (Sym2 V))), - $|A|$ is the number of edges in $A$ (A.card), - $c(V, A)$ is the number of connected components of $(V, A)$ (Fintype.card (SimpleGraph.fromEdgeSet A).ConnectedComponent), and - the subgraph is tested for bipartiteness using SimpleGraph.IsBipartite.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

open scoped Classical in
/-- The bipartite subgraph polynomial 8^{-|V|} ∑_{A ⊆ E, (V,A) bipartite} (-2)^{|A|} 8^{k(V,A)}. -/
noncomputable def bipartite_subgraph_magic_poly {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] : ℝ := (1 / (8 ^ Fintype.card V : ℝ)) *
    ∑ A ∈ G.edgeFinset.powerset,
      if (SimpleGraph.fromEdgeSet (A : Set (Sym2 V))).IsBipartite then
        ((-2 : ℝ) ^ A.card) * (8 : ℝ) ^ (Fintype.card (SimpleGraph.fromEdgeSet (A : Set (Sym2 V))).ConnectedComponent)
      else 0
See it in the graphDiscuss this resultChallenge it