AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Subcubic Triangle-Free Non-Bipartite Graphs Do Not Always Admit Independent Partitions with Complementary Component Order at Most Three

low tier2026-11-05OP-1087reviewed by Codex中文版

Abstract

In the study of graph partitions and cut problems in subcubic graphs, Question 5.4 of arXiv:2611.05178 asks whether every finite simple graph with maximum degree at most 3 and odd girth exactly 5 admits a partition of its vertex set into disjoint subsets $L$ and $R$ such that $L$ is an independent set and every connected component of the induced subgraph on $R$ has order at most 3. This question is answered in the negative. A counterexample is formalized and mechanically verified in Lean 4 as the theorem subcubic_odd_girth_five_partition_component_le_three_negation. The counterexample has vertices $0,\ldots,7$, with edges between consecutive vertices modulo 8 and between vertices four apart. It is cubic and triangle-free, and $0,1,2,3,4,0$ is a 5-cycle, so its odd girth is exactly 5. By establishing that every independent set $L$ leaves at least one vertex whose reachable component in the complementary induced subgraph exceeds order 3, the universal claim is contradicted. This result delineates the boundary of defective vertex partitions in sparse graphs, contrasting with the bipartite case where such partitions always exist.

1. Introduction

Graph partition problems with structural constraints on the parts form a central area of study in structural graph theory and combinatorial optimization. A recurring objective is to partition the vertex set $V(G)$ of a graph $G$ into two disjoint classes, $V(G) = L \cup R$, such that the set $L$ is independent (inducing no edges) while the complementary induced subgraph $G[R]$ satisfies controlled structural conditions, such as having bounded maximum degree, bounded degeneracy, or bounded connected component sizes. Such partitions generalize proper vertex colorings and are closely connected to maximum cut problems, where one seeks large bipartite subgraphs or decompositions that isolate dense subgraphs into small, manageable pieces.

In arXiv:2611.05178, titled "Weighted Max Cut in Subcubic Graphs", structural decompositions and cut properties are investigated within the class of subcubic graphs, which are graphs having maximum degree at most 3. In Section 5 of that work, Question 5.4 poses the following open problem: Does every subcubic graph $G$ of odd girth exactly 5 admit a partition $V(G) = L \cup R$ such that $L$ is an independent set and every component of $G[R]$ has order at most 3?

The condition that $G$ has odd girth exactly 5 means that the length of the shortest cycle of odd length in $G$ is precisely 5. Equivalently, $G$ contains no cycle of length 3 (it is triangle-free) and contains at least one cycle of length 5, which in particular implies that $G$ is not bipartite (since bipartite graphs contain no odd cycles whatsoever). The restriction to subcubic graphs provides a sparse regime where independent sets and induced paths or trees have been extensively studied. Requiring every connected component of $G[R]$ to have order at most 3 is a strong boundedness requirement: it forces $G[R]$ to be a disjoint union of isolated vertices, isolated edges ($K_2$), paths of length 2 ($P_3$), or triangles ($K_3$), although triangles are already excluded by the girth requirement.

Prior to this work, several baseline cases were understood. In the bipartite setting, the answer is immediately positive: every bipartite graph admits a 2-coloring $V(G) = V_1 \cup V_2$ where both $V_1$ and $V_2$ are independent sets. Setting $L = V_1$ leaves $R = V_2$, in which every connected component is an isolated vertex of order 1, well within the bound of 3. This fact has been formally verified in Lean under the theorem name subcubic_partition_component_le_three_of_isBipartite. Furthermore, for trivially small graphs on at most 3 vertices, any choice of independent set (including the empty set) leaves a complement of total size at most 3, guaranteeing that every component of $G[R]$ has order at most 3, a property verified in subcubic_partition_component_le_three_of_card_le_three.

Thus, Question 5.4 in arXiv:2611.05178 asks whether the presence of 5-cycles in a triangle-free subcubic graph can always be accommodated by selecting an independent set $L$ that shatters the remainder of the graph into components of order at most 3.

This post presents the formal refutation of Question 5.4. We report on the theorem subcubic_odd_girth_five_partition_component_le_three_negation, which demonstrates that the universal statement is false. Specifically, there exists a finite simple graph that has maximum degree at most 3, is clique-free of order 3, and is not bipartite, yet admits no independent set whose complement consists only of components of order at most 3. The formal proof uses the graph on $\mathbb Z/8\mathbb Z$ with edges $\{i,i+1\}$ and $\{i,i+4\}$ for every $i$. It verifies the degree and triangle conditions and checks that every independent set leaves a connected component of order at least 4 in the complement. The cycle $0,1,2,3,4,0$ shows directly that this particular graph has odd girth 5.

2. Preliminaries

We work in the framework of finite simple graphs as formalized in Lean 4. Throughout this post, let $V$ be a finite type equipped with decidable equality.

Definition 1 (Simple Graph, SimpleGraph). A simple graph $G$ on a vertex type $V$ consists of a symmetric and irreflexive binary relation $G.\mathrm{Adj} : V \to V \to \mathrm{Prop}$. Symmetry means that for all $u, v \in V$, $G.\mathrm{Adj}(u, v) \leftrightarrow G.\mathrm{Adj}(v, u)$, and irreflexivity means that for all $u \in V$, $\neg G.\mathrm{Adj}(u, u)$. In Lean, the relation is assumed to be decidable.

Definition 2 (Maximum Degree, SimpleGraph.maxDegree). For a finite simple graph $G$, the degree of a vertex $v \in V$ is the cardinality of its neighbor set, $\deg(v) = |\{ u \in V \mid G.\mathrm{Adj}(v, u) \}|$. The maximum degree of $G$, denoted $\Delta(G)$ or SimpleGraph.maxDegree, is the maximum of $\deg(v)$ over all $v \in V$. A graph is said to be subcubic if $\Delta(G) \le 3$. *Remark.* In Lean, the condition is formulated as a weak inequality $\Delta(G) \le 3$, allowing graphs with maximum degree strictly less than 3 as well as graphs that achieve degree 3.

Definition 3 (Clique-Free Graphs, SimpleGraph.CliqueFree). For a natural number $n$, a graph $G$ is clique-free of order $n$, denoted SimpleGraph.CliqueFree, if there is no subset of $n$ vertices in $V$ that are pairwise adjacent. For $n = 3$, SimpleGraph.CliqueFree of order 3 expresses that $G$ contains no 3-clique, meaning $G$ is triangle-free. *Remark.* The condition forbids complete subgraphs isomorphic to $K_3$. It does not prevent cycles of length 5 or greater.

Definition 4 (Bipartite Graphs, SimpleGraph.IsBipartite). A graph $G$ is bipartite, denoted SimpleGraph.IsBipartite, if there exists a 2-coloring of the vertices such that no two adjacent vertices share the same color. A graph has odd cycles if and only if it is not bipartite. *Remark.* A graph that satisfies both SimpleGraph.CliqueFree for order 3 and the negation of SimpleGraph.IsBipartite cannot have an odd cycle of length 3, and hence its shortest odd cycle must have length at least 5. When the graph contains a 5-cycle, its odd girth is exactly 5.

Definition 5 (Induced Subgraph, SimpleGraph.induce). Given a subset of vertices $S \subseteq V$, the induced subgraph $G[S]$, formalized in Lean as SimpleGraph.induce, is the simple graph with vertex type given by the subtype $\{ v : V // v \in S \}$, where two vertices $\langle u, h_u \rangle$ and $\langle v, h_v \rangle$ are adjacent if and only if $G.\mathrm{Adj}(u, v)$.

Definition 6 (Independent Set). A subset $L \subseteq V$ is an independent set of $G$ if no two distinct vertices in $L$ are adjacent. In Lean, this is expressed algebraically by the equality where SimpleGraph.induce on $L$ is equal to the empty graph $\bot$ (the bottom element of the lattice of simple graphs on $L$). This is equivalent to stating that for all $x, y \in L$ with $x \neq y$, $\neg G.\mathrm{Adj}(x, y)$.

Definition 7 (Connected Components and Order, SimpleGraph.ConnectedComponent). Two vertices $u, v$ in a graph $H$ are reachable from one another if there exists a walk from $u$ to $v$ in $H$. The connected components of $H$ are the equivalence classes of the reachability relation, represented by the quotient type SimpleGraph.ConnectedComponent. For an induced subgraph on the complement of $L$, the components are the connected components of $G[L^c]$. The order of a component $C$ is its cardinality, denoted $|C|$. *Remark.* In Lean, component sizes can be measured using finite type cardinality or general natural cardinality, with standard library equivalence lemmas relating them. The condition that every connected component in the complement has order at most 3 is written using a universal quantifier over all components $C$, requiring the cardinality of $C$ to be at most 3.

Definition 8 (Reachable Component Subgraph). Given an independent set $L$ and a vertex $v \in L^c$, the connected component of $v$ in $G[L^c]$ can be represented as the finset of all vertices reachable from $v$: $$S = \{ w \in L^c \mid (G[L^c]).\mathrm{Reachable}(v, w) \}$$ In Lean, this finset is constructed by filtering the universal vertex set over the condition that $v$ and $w$ are connected by a path in the induced subgraph on the complement.

3. Main result

The counterexample in the Lean proof refutes Question 5.4 from arXiv:2611.05178. Its theorem is stated for the larger class of triangle-free, non-bipartite subcubic graphs; those conditions by themselves only imply odd girth at least 5. For the particular graph used in the proof, the 5-cycle exhibited below gives odd girth exactly 5.

Theorem (subcubic_odd_girth_five_partition_component_le_three_negation). It is not the case that every finite simple graph $G = (V, E)$ with maximum degree $\Delta(G) \le 3$, clique-free of order 3, and not bipartite admits a partition of its vertex set into an independent set $L$ and a complement $R = L^c$ such that every connected component of the induced subgraph $G[R]$ has order at most 3: $$\neg \Big( \forall (V, G), \Delta(G) \le 3 \land G.\mathrm{CliqueFree}(3) \land \neg G.\mathrm{IsBipartite} \implies \exists L \subseteq V, G[L] = \emptyset \land \forall C \in \pi_0(G[L^c]), |C| \le 3 \Big)$$

In Lean, the theorem is formalized as the negation of the universal proposition over all finite types $V$ with decidable equality and simple graphs $G$ on $V$ with decidable adjacency that under the hypotheses SimpleGraph.maxDegree at most 3, SimpleGraph.CliqueFree of order 3, and the negation of SimpleGraph.IsBipartite, there exists a finset representing $L$ such that SimpleGraph.induce on $L$ is empty and every SimpleGraph.ConnectedComponent of the complement has cardinality at most 3.

In addition to this refutation, earlier formalizations establish positive counterparts for related families that clarify the scope of the problem:

- Bipartite Graphs (subcubic_partition_component_le_three_of_isBipartite). Every bipartite finite simple graph admits a partition of its vertex set into an independent set $L$ and a complement $R = L^c$ such that every connected component of the induced subgraph $G[R]$ has order at most 3. This theorem demonstrates that the failure established in the main theorem requires non-bipartiteness: in any bipartite graph, the vertex set can be partitioned into two independent sets $V_1$ and $V_2$, so taking $L = V_1$ guarantees that every component of $G[R] = G[V_2]$ is an isolated vertex of order 1, which strictly satisfies the bound of 3.

- Small Graphs (subcubic_partition_component_le_three_of_card_le_three). Every finite simple graph on at most 3 vertices admits a partition of its vertex set into an independent set $L$ and a complement $R = L^c$ such that every connected component of the induced subgraph $G[R]$ has order at most 3. This result confirms that any counterexample must have order strictly greater than 3. For any graph with $|V| \le 3$, selecting $L = \emptyset$ leaves $|R| \le 3$, ensuring that no component can possibly exceed order 3 regardless of the edge structure or bipartiteness.

These positive cases locate the counterexample outside the bipartite class and show only the elementary lower bound of four vertices on the order of any counterexample.

Theorem subcubic_odd_girth_five_partition_component_le_three_negation (Lean 4, verified)
theorem subcubic_odd_girth_five_partition_component_le_three_negation :
    ¬ (∀ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],
      G.maxDegree ≤ 3 → G.CliqueFree 3 → ¬G.IsBipartite →
        ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧
          ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent,
            open scoped Classical in Fintype.card C ≤ 3)

4. Proof

We begin with the overall idea of the proof, then state and prove the intermediate lemmas, and finally assemble them into the complete argument matching the Lean formalization.

The proof of subcubic_odd_girth_five_partition_component_le_three_negation proceeds by contradiction. Assuming the universal claim holds, we denote it by $H$: $$H : \forall \{V : \mathrm{Type}^*\} [ \mathrm{Fintype}\ V ] [ \mathrm{DecidableEq}\ V ] (G : \mathrm{SimpleGraph}\ V) [ \mathrm{DecidableRel}\ G.\mathrm{Adj} ],$$ $$G.\mathrm{maxDegree} \le 3 \to G.\mathrm{CliqueFree}\ 3 \to \neg G.\mathrm{IsBipartite} \to \exists L : \mathrm{Finset}\ V, G.\mathrm{induce}(L) = \bot \land \forall C, |C| \le 3$$ We instantiate $H$ with the eight-vertex graph $G_0$ on $\mathbb Z/8\mathbb Z$ whose edges are $\{i,i+1\}$ and $\{i,i+4\}$ for all $i$, with arithmetic modulo 8. Each vertex has neighbors $i-1,i+1,i+4$. The cycle $0,1,2,3,4,0$ has length 5; together with triangle-freeness below, it proves odd girth exactly 5. To apply $H$ to $G_0$, the formal proof verifies the three antecedent conditions via Lemmas 1, 2, and 3 below.

Lemma 1 (Maximum Degree Bound). The counterexample graph $G_0$ has maximum degree at most 3. *Proof.* In Lean, the maximum degree is defined as the supremum of vertex degrees over the finite vertex set $V$. For each vertex $v \in V$, the cardinality of its neighborhood $\{ u \in V \mid G_0.\mathrm{Adj}(v, u) \}$ is evaluated by computation. Since the neighborhood size is at most 3 for every vertex, the maximum degree satisfies $\Delta(G_0) \le 3$.

Lemma 2 (Absence of Triangles). The counterexample graph $G_0$ is clique-free of order 3 (SimpleGraph.CliqueFree for order 3). *Proof.* A graph is clique-free of order 3 if there is no set of 3 mutually adjacent vertices. Lean settles this property by exhaustively checking all 3-element subsets of the vertex set. For each triple of vertices $\{u, v, w\}$, the decidable adjacency relation verifies that at least one pair is non-adjacent. Thus no triangle exists in the graph.

Lemma 3 (Non-Bipartiteness). The counterexample graph $G_0$ is not bipartite (the negation of SimpleGraph.IsBipartite). *Proof.* Bipartiteness is equivalent to 2-colorability. Lean checks by finite computation that every assignment of two colors to the eight vertices gives the same color to some adjacent pair. This contradicts a proper 2-coloring. Independently, the displayed 5-cycle makes the non-bipartiteness and exact odd girth visible.

With these three lemmas established, instantiating $H$ with $G_0$ yields a finite subset of vertices $L$ together with two hypotheses:

  1. $h_{\mathrm{ind}} : G_0.\mathrm{induce}(L) = \bot$, asserting that $L$ is an independent set.
  2. $h_{\mathrm{comp}} : \forall C : (G_0.\mathrm{induce}(L^c)).\mathrm{ConnectedComponent}, |C| \le 3$, asserting that every connected component of the complement has cardinality at most 3.

To make the independence condition computationally usable, the proof extracts pairwise non-adjacency:

Lemma 4 (Pairwise Non-Adjacency). Let $L$ be a finset of vertices such that SimpleGraph.induce on $L$ is equal to $\bot$. Then for all $x \in L$ and $y \in L$ with $x \neq y$, $\neg G_0.\mathrm{Adj}(x, y)$. *Proof.* Let $x, y \in L$ with $x \neq y$, and suppose for contradiction that $G_0.\mathrm{Adj}(x, y)$. By the definition of adjacency in induced subgraphs, the corresponding subtype elements $\langle x, h_x \rangle$ and $\langle y, h_y \rangle$ are adjacent in the induced subgraph on $L$. Substituting $h_{\mathrm{ind}}$, this implies that these vertices are adjacent in $\bot$. However, the empty graph $\bot$ contains no adjacent pairs, yielding a contradiction. Hence $x$ and $y$ cannot be adjacent. We denote this pairwise non-adjacency condition by $h_L$.

Next, the proof relies on a key structural property of the graph $G_0$:

Lemma 5 (Obstruction to Small Components). For any subset $L$ of vertices of $G_0$ satisfying the pairwise non-adjacency condition $h_L$, there exists a vertex $v \in V$ satisfying a reachability obstruction property $h_v$ in the complement $L^c$. *Proof.* Lean proves this finite assertion with decide: for each of the $2^8$ subsets, if the subset is independent, it checks that some vertex in the complement has at least four reachable vertices there. The lemma returns such a vertex and the corresponding cardinality bound. This is an exhaustive verification of the stated obstruction, rather than a classification of independent sets.

Lemma 6 (Cardinality Contradiction). Let $G_0$ be the counterexample graph, let $L \subseteq V$, and let $v \in L^c$ be a vertex satisfying the obstruction property $h_v$. Define the reachable set: $$S = \{ w \in L^c \mid (G_0[L^c]).\mathrm{Reachable}(v, w) \}$$ If every connected component $C$ of $G_0[L^c]$ satisfies $|C| \le 3$, then a contradiction follows. *Proof.* By construction, $S$ is precisely the vertex set of the connected component containing $v$ in the induced subgraph $G_0[L^c]$. The condition $h_v$ ensures that $S$ contains at least 4 distinct vertices. In Lean, the component corresponding to $v$ is identified as an element of the quotient type of connected components of the complement. The hypothesis that all components have cardinality at most 3 forces $|C| \le 3$, which contradicts the existence of at least 4 reachable vertices in $S$. The lemma formalizes this arithmetic contradiction and derives a contradiction.

Combining the Steps: The proof of subcubic_odd_girth_five_partition_component_le_three_negation puts these pieces together in the following sequence: 1. Assume $H$ by introduction. 2. Apply $H$ to $G_0$, supplying Lemma 1 (maximum degree bound), Lemma 2 (absence of triangles), and Lemma 3 (non-bipartiteness). 3. Obtain the independent finset $L$, the equality $h_{\mathrm{ind}} : G_0.\mathrm{induce}(L) = \bot$, and the component bound $h_{\mathrm{comp}} : \forall C, |C| \le 3$. 4. From $h_{\mathrm{ind}}$, construct $h_L$ via Lemma 4, showing that $L$ contains no adjacent pairs. 5. Apply Lemma 5 with $L$ and $h_L$ to obtain a witness vertex $v$ and proof $h_v$. 6. Translate the component cardinality bound to natural number cardinality, producing $h_{\mathrm{comp}}' : \forall C, |C| \le 3$. 7. Define $S$ by filtering the vertex set for elements reachable from $v$ in the induced subgraph on $L^c$. 8. Apply Lemma 6 with $G_0$, $L^c$, $v$, $S$, $h_v$, the filter membership characterization, and $h_{\mathrm{comp}}'$. 9. The resulting contradiction completes the refutation.

5. Discussion

The theorem subcubic_odd_girth_five_partition_component_le_three_negation answers Question 5.4 of arXiv:2611.05178 in the negative. It establishes that subcubic graphs with odd girth 5 do not always admit a partition into an independent set and an induced subgraph whose components have order at most 3.

It is instructive to examine how this result positions itself relative to the broader theory of graph partitions with component-order constraints:

1. Contrast with Bipartite Graphs. As recorded by subcubic_partition_component_le_three_of_isBipartite, bipartite graphs unconditionally admit such partitions with component order at most 1 (since both partition classes are independent). In bipartite graphs, there are no odd cycles, meaning the chromatic number is 2. The question posed in arXiv:2611.05178 sought to determine whether permitting the shortest odd cycle to have length 5 would allow a slight relaxation—from independent components (order 1) to components of order at most 3—to absorb the non-bipartite obstructions. The eight-vertex counterexample proves that order 3 is insufficient for this class; the formal proof establishes the obstruction by a finite check.

2. Component Order Threshold. A natural follow-up question raised by this refutation is whether a larger constant bound on component order holds. That is, does there exist an integer $k \ge 4$ such that every subcubic graph of odd girth 5 admits a partition $V = L \cup R$ with $L$ independent and every component of $G[R]$ having order at most $k$? If no such universal constant $k$ exists, one would want to determine whether the maximum component order in $G[R]$ can grow arbitrarily large with the number of vertices, or whether it can be bounded as a function of graph invariants such as treewidth or maximum degree.

3. Higher Odd Girth. Another direction concerns strengthening the girth hypothesis. Question 5.4 specifically fixed the odd girth to be exactly 5. What happens for subcubic graphs of odd girth 7, 9, or larger? Increasing the odd girth excludes short odd cycles, although even cycles may still occur. Does there exist an odd girth threshold $g_{\mathrm{odd}} \ge 7$ beyond which every subcubic graph admits an independent set with complementary component order at most 3, or does the counterexample construction generalize to higher odd girths?

4. Algorithmic and Cut Implications. In the context of weighted max cut problems studied in arXiv:2611.05178, independent-complement partitions with small components provide structural tools for divide-and-conquer strategies and approximation algorithms. The non-existence of partitions with component order at most 3 indicates that algorithm designs relying on such partitions must either tolerate components of order 4 or greater, or utilize alternative structural decompositions.

Why it is research-level

  • refutes OP-1087 (Partition of Odd-Girth 5 Subcubic Graphs with Component Order at Most Three)

Lean declarations

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2611.05178 — Weighted Max Cut in Subcubic Graphs

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Codex. Only the Lean is verified; the prose is a reading of it.