Weighted Max Cut in Subcubic Graphs

Introduction

Let $G=(V,E,w)$ be a finite simple edge-weighted graph with weight function $w:E\to[0,\infty)$. The girth of $G$ is the length of its shortest cycle. The odd girth of $G$ is the length of its shortest odd cycle. For a partition $(L,R)$ of $V(G)$, the cut $(L,R)$ is the spanning bipartite subgraph consisting of the edges between $L$ and $R$. For disjoint vertex sets $A,B\subseteq V(G)$, let $E(A,B)$ denote the set of edges with one endpoint in $A$ and the other in $B$, and let $G[A,B]$ denote the spanning bipartite subgraph with edge set $E(A,B)$. Given a cut $(L,R)$, an edge is internal if it belongs to $E(G[L])\cup E(G[R])$ and external or crossing if it belongs to $E(L,R)$. The Max Cut problem asks for a cut of maximum total weight, which we denote by $\operatorname{mc}(G,w)$. In the unweighted case, every edge has weight one, and we write $\operatorname{mc}(G)$ for the maximum number of edges in a cut.

A graph is cubic if every vertex has degree exactly three, and subcubic if every vertex has degree at most three. Computing a maximum cut is NP-hard even for triangle-free cubic graphs [11]. Moreover, for every $\varepsilon>0$, a polynomial-time approximation algorithm for Max Cut on cubic graphs with approximation ratio $\frac{331}{332}+\varepsilon$ would imply P = NP [2]. On the positive side, Halperin, Livnat, and Zwick [6] gave a 0.9326-approximation algorithm for unweighted Max Cut on subcubic graphs, using semidefinite programming and local improvement, and a combinatorial $\frac{22}{27}$-approximation algorithm for cubic graphs. These approximation ratios compare the cut returned by an algorithm with an optimal cut; our focus is on lower bounds relative to the total edge weight.

Subcubic graphs combine computational difficulty with structural restrictions that yield strong lower bounds. Every subcubic graph $G$ satisfies $\operatorname{mc}(G)\ge\frac{2}{3}|E(G)|$, with equality for $K_3$ and $K_4$. Hopkins and Staton [7] proved that every triangle-free cubic graph has a cut containing at least $\frac{4}{5}$ of its edges. Bondy and Locke [3] extended this bound to triangle-free subcubic graphs. Xu and Yu [10] characterized the seven connected triangle-free subcubic graphs for which equality holds. Zhu [12] subsequently proved that every 2-connected triangle-free subcubic graph outside the exceptional family of Xu and Yu satisfies $\operatorname{mc}(G)\ge\frac{17}{21}|E(G)|$.

For weighted graphs, Poljak and Turzík [9] proved the general lower bound $\operatorname{mc}(G,w) \ge\frac{1}{2}w(G) + \frac{1}{4}w(T_{\min})$, where $G$ is connected and $T_{\min}$ is a minimum-weight spanning tree of $G$. Gutin and Yeo [5] developed a structural approach that strengthens the inequality of Poljak and Turzík and yields the following bound for triangle-free subcubic graphs.

They also conjectured that the unweighted $\frac{4}{5}$ bound extends to arbitrary nonnegative edge weights.

A stronger weighted bound is implicit in a result of Kardoš, Král’, and Volec, stated in terms of probability distributions on cuts rather than weighted Max Cut.

Their proof shows that one may take $g_0=637{,}789$. For a fixed graph $G$, this distributional statement is equivalent to the weighted Max Cut bound $\operatorname{mc}(G,w) \ge0.88672w(G)$ holding for every nonnegative edge weighting $w$. The forward implication follows by linearity of expectation. Conversely, after normalizing nonzero edge weightings so that $w(G)=1$, the finite minimax theorem yields a single probability distribution on cuts under which every edge crosses with probability at least 0.88672.

In this paper, we improve the bound in Theorem 1.1 from $\frac{8}{11}$ to $\frac{15}{19}$.

We obtain further improvements under additional odd-girth assumptions.

Thus Theorem 1.6 establishes Conjecture 1.2 for subcubic graphs of odd girth at least 9. Although our bounds remain below the constant 0.88672 in Theorem 1.3, they improve the weighted guarantee under relatively small odd-girth assumptions, allowing short even cycles.

Section 2 establishes a general lower bound (Theorem 2.2) for weighted Max Cut in cubic graphs admitting a partition with specified bipartite component structure. In Section 3, we apply the general bound to an unweighted maximum-cut partition and combine the resulting inequality with the weight of that partition to prove Theorem 1.4. Section 4 uses additional partition structure to prove Theorem 1.5 and Theorem 1.6.

Setup and General Lower Bound

Applying a strategy in [5], if $G$ is a subcubic graph of arbitrary odd girth, we may extend $G$ to a cubic graph with the same odd girth and weighted max-cut.

Throughout the remainder of this paper, let $G$ be a cubic graph with fixed odd girth. By Lemma 2.1, all weighted max-cut results proved for cubic graphs extend to subcubic graphs with fixed odd girth.

Consider $(L,R)$, an unweighted max-cut partition of $G$. Since the cut is maximum, every vertex has at least two neighbors on the opposite side, and hence the internal edges form a matching. Write

For $i \in\{2,3\}$, let

Thus, the indices refer to degrees in the crossing subgraph $G[L,R]$. Partition the crossing edges as

After these random choices, place the vertices of each component of $G[L]$ in $(L',R')$ so as to maximize the total crossing weight of the edges incident with that component. Since distinct components of $G[L]$ have no edges between them, these optimizations may be performed independently.

For an edge component $D=uv$, we say a placement of $D$ is proper if $u$ and $v$ lie on opposite sides of $(L',R')$, so that the edge $uv$ is crossing.

Suppose a component $D$ of $G[L]$ is adjacent to $k\le3$ components $C_1,\ldots,C_k$ of $G[R]$. If $D$ is a singleton vertex there are two possible placements of its vertices in $L'$ and $R'$. When $D$ is an edge component, there are two proper placements of $D$ in $L'$ and $R'$.

Since $G[D\cup C_i]$ is bipartite, the placement of $C_i$ determines a unique (proper) placement of $D$ for which all edges in $E(D,C_i)$ are crossing. Call this the placement determined by $C_i$.

Proof of Claim 1. Consider the three possible cases for $k$.

• If $k=1$, use the placement determined by $C_1$. All edges (including $uv$) will be crossing.

• If $k=2$, use the common (proper) placement when the placements determined by $C_1$ and $C_2$ agree. Otherwise, choose uniformly between the two (proper) placements of $D$. The placement determined by each $C_i$ is used with probability $3/4$, and $uv$ will always be crossing.

• If $k=3$, use the placement determined by at least two of the three components. For any fixed $C_i$, its placement is not used only when both of the other components prefer the opposite placement, which occurs with probability $1/4$.

Thus, in every case, each edge in $E(D,C_i)$ is crossing with probability at least $3/4$. Linearity of expectation gives the claim. □

Let $D$ be the isolated vertex $v\in L_3$. Since $v$ has degree three, it is adjacent to at most three components of $G[R]$. Applying Claim 1 shows that the expected crossing weight among the three edges incident with $v$ is at least three quarters of the total weight.

Next let $D=uv$ be an edge component of $G[L]$. Since $G$ is cubic, each of $u$ and $v$ has exactly two neighbors in $R$. Write

First suppose that $D$ is adjacent to at most three components of $G[R]$. Applying Claim 1 gives expected external crossing weight at least

Since $uv$ is always crossing in a proper placement, the expected contribution of $D$ and its external edges is at least

It remains to consider the case in which $D=uv$ is adjacent to four distinct components of $G[R]$. Unlike the case when $D$ neighbors at most 3 components, we cannot always guarantee $uv$ to be crossing. In this case, the four neighbors of $u,v$ in $R$ have four independent random sides in $(L',R')$. Let $u_1,u_2$ be the external neighbors of $u$ in $R$, and let $v_1,v_2$ be the external neighbors of $v$ in $R$. We give a rule for placing $u$ and $v$. Call $u$ rigid if $u_1,u_2$ lie on the same side in $(L',R')$ and flexible otherwise, and $v$ analogously. If an endpoint, $u$ or $v$, is rigid, prescribe that it be placed opposite the common side of its two external neighbors. If exactly one endpoint is flexible, place it opposite the rigid endpoint, so that $uv$ crosses. If both endpoints are flexible, choose uniformly between the two proper placements of $u$ and $v$.

Since the sides of $u_1,u_2$ are independent fair choices, $\Pr(u\text{ is rigid})=\Pr(u\text{ is flexible})=\frac{1}{2}$. When $u$ is rigid, both edges $uu_1,uu_2$ cross. When $u$ is flexible, the two neighbors lie on opposite sides, so exactly one of $uu_1,uu_2$ crosses. Therefore

The same calculation applies to all four external edges. Their expected total crossing weight is therefore

For the edge $uv$, if at least one endpoint is flexible, our rule makes $uv$ crossing. The rigidity events for $u$ and $v$ are independent, so this occurs with probability $\frac{3}{4}$. If both endpoints are rigid, which occurs with probability $1/4$, their two prescribed sides are opposite with probability $1/2$. Hence

Thus in this final case the comparison rule has expected crossing weight

Since we actually place $u,v$ so as to maximize the weighted crossing contribution of the component $D$, the optimized placement performs at least as well as the expected crossing weight. Thus, we obtain

Triangle Free Max Cut

For a maximum-cut partition, both sides consist of edges and isolated vertices, so we can apply Theorem 2.2 in either direction.

Proof. Since $(L,R)$ is a maximum-cut partition, every vertex has at most one neighbor on its own side. In particular, both $G[L]$ and $G[R]$ are collections of bipartite components. Moreover, for any component $C_L$ of $G[L]$ and any component $C_R$ of $G[R]$, the graph $G[C_L\cup C_R]$ has at most four vertices. Since $G$ is triangle-free, $G[C_L\cup C_R]$ is bipartite. Thus Theorem 2.2 applies to $(L,R)$ and gives

Applying the same theorem with the roles of $L$ and $R$ reversed gives

Averaging these two inequalities, we obtain

The original partition gives a strong bound when $w(M)$ is small, while Lemma 3.1 improves as $w(M)$ increases. Together these two bounds give an improved universal bound.

Proof. By Lemma 2.1, it suffices to consider the case that $G$ is cubic. Let $(L,R)$ be a maximum-cut partition. By Lemma 3.1,

On the other hand, deleting the internal edges $M$ leaves the bipartite graph $G-M$ with bipartition $(L,R)$. Hence

Taking the convex combination of (1) and (2) with coefficients $\frac{16}{19}$ and $\frac{3}{19}$, respectively, gives

Max Cut with Higher Odd Girth

Here we provide an improved bound for subcubic graphs with odd girth at least seven and prove Conjecture 1.2 for graphs with odd girth at least nine. First, we prove some structural lemmas about an arbitrary max-cut $(L,R)$ of a triangle-free cubic graph.

Proof. Suppose $vu'_1u'_2u_2$ does not form a 5-cycle, namely, $u'_1 \not\sim u'_2$. Since $G$ is triangle-free, $u_1 \not\sim u_2$. Thus, swapping $v,u'_1,u'_2$ and $u_1,u_2$ increases the number of cut edges, contradicting the maximality of $(L,R)$.

Special Max Cut Partitions

For the rest of the paper, we consider two particular max-cut partitions, each excluding a local configuration on one side. Constructing the second partition from the first allows us to bound the specific weights in terms of the first.

Begin with an arbitrary max-cut partition. Suppose that, for the current partition $(L,R)$, there is a vertex $v \in R$ with three neighbors $u_1, u_2, u_3 \in L_2$. Swap $v$ and $u_1,u_2,u_3$.

Since $G$ is triangle-free, this operation preserves the number of crossing edges, and hence the resulting partition is again a maximum-cut partition. Moreover, the size of the $R$-side increases by two. Repeat this swapping process until there are no more vertices in $R$ with three neighbors in $L_2$. If $R$ is maximal with respect to these swaps, we say $(L,R)$ is an $R$-maximal max-cut partition. Fix an $R$-maximal max-cut partition $(L,R)$. By construction, no vertex $v \in R$ has three neighbors in $L_2$.

Starting from this partition $(L,R)$, perform the analogous swapping operation in the opposite direction. If there is a vertex $v \in L$ with three neighbors $u_1,u_2,u_3 \in R_2$, swap $v$ and $u_1,u_2,u_3$. Again, this preserves the number of crossing edges. Repeat this swapping process until there are no more vertices in $L$ with three neighbors in $R_2$, to create a new partition $(L',R')$. If $L'$ is maximal with respect to these swaps, we say $(L',R')$ is an $L$-maximal max-cut partition. Fix $(L',R')$, an $L$-maximal max-cut partition resulting from the $R$-maximal max-cut partition $(L,R)$. Then no vertex $v \in L'$ has three neighbors in $R'_2$.

During the construction of $(L',R')$, internal edges are only added to the $L'$-side and removed from the $R'$-side. Consequently,

Odd Girth at Least Seven

Let $G$ be a triangle-free cubic graph with odd girth at least 7. Consider the max-cut partitions $(L, R)$ and $(L', R')$ defined in § 4.1.

Following the framework of [1], we will define an auxiliary conflict graph $C$ with vertex set $L_2 \subseteq L$ and a corresponding conflict graph $C'$ with vertex set $R'_2 \subseteq R'$. Given $u, v \in L_2$, we say $u \sim_C v$ if $u \sim_G v$ or if $u$ and $v$ have a neighbor in the same component of $G[R]$ (which consists of $M_R$ and singleton vertices). Define $C'$ analogously for incidence of $u, v \in R'_2$ with components of $G[L']$.

An independent set in $C$ specifies vertices that can be moved from $L$ to $R$ simultaneously so that no edge of $M_L$ has both endpoints moved, and no component of $G[R]$ gains more than one vertex from $L$. This keeps the resulting components on the $R$-side small, allowing us to apply Theorem 2.2.

Proof. To prove (1), consider $v \in V(C) = L_2$. The vertex $v$ has one neighbor in $L_2$ which contributes one edge in $C$. Also, $v$ has two neighbors in $R$; let $u$ be one of them. If $u \in R_3$, then by the $R$-maximality of $(L, R)$, $u$ has at most one other neighbor in $L_2$, providing at most one more $C$-neighbor. If $u \in R_2$, then let $w$ be its unique neighbor in $R_2$. By Lemma 4.1, $u$ has no neighbors in $L_2$ other than $v$ and $w$ has at most one neighbor in $L_2$. Thus the component of $u$ provides at most one more $C$-neighbor. Together, $d_C(v) \le3$.

To prove (2), suppose $C$ has a $K_4$ subgraph. Since each vertex has degree at most 3, and one neighbor comes from the matching edges of $M_L$, the $K_4$ must consist of $u_1, u_2$ and $v_1, v_2$ where $u_1u_2, v_1v_2 \in M_L$. If $u_1 \sim_C v_1, v_2$ then $u_1$ is incident with the same component as $v_1$ in $R$; call that component $C_1 \subseteq R$. Also $u_1$ is incident with the same component as $v_2$ in $R$; call that component $C_2 \subseteq R$.

If $C_1$ and $C_2$ are both singleton vertices, then $u_1 \cup C_1 \cup C_2 \cup v_1v_2$ induce a 5-cycle in $G$ which contradicts the odd girth of $G$.

If $C_1$ and $C_2$ are both edges in $M_R$, then $u_1 \in L_2$ has two neighbors in $R_2$ which contradicts Lemma 4.1.

Thus we may assume that $C_1$ is an edge of $M_R$ and $C_2$ is an isolated vertex belonging to $R_3$.

Note that $u_2$ is incident with the same component as $v_1$ in $R$; call that component $C'_1 \subseteq R$. Also $u_2$ is incident with the same component as $v_2$ in $R$; call that component $C'_2 \subseteq R$. By symmetry, one of $C'_1, C'_2$ consists of an edge of $M_R$, and the other is an isolated vertex of $G[R]$ belonging to $R_3$. To ensure $u_2$ does not violate Lemma 4.1, $C'_1$ must be an isolated vertex belonging to $R_3$, and $C'_2$ must be an edge of $M_R$.

Let $C_2 = \{w\}$, where $w \in R_3$ is adjacent to $u_1, u_2 \in L_2$. Since $(L, R)$ is $R$-maximal, the third neighbor of $w$ belongs to $L_3$. Moreover, $u_1$ and $u_2$ have neighbors $u'_1, u'_2 \in R_2$, respectively, in the components $C_1$ and $C'_2$. Lemma 4.2 therefore implies that $wu_1u'_1v_2v_1u'_2u_2w$ is a 5-cycle. However, this contradicts the assumption that $G$ has odd girth at least 7.

Thus $C$ contains no $K_4$.

The same argument shows that $C'$ contains no $K_4$.

By Brooks’ Theorem, a $K_4$-free graph with max degree 3 is 3-colorable.

The three-coloring lets us choose a set of vertices that can be moved simultaneously while capturing at least one third of the crossing weight incident with $L_2$.

and

Moreover, the sets $S_L$ and $S_R$ may be chosen so that

Proof. Consider $C$, the conflict graph for $L_2$. By Lemma 4.3, the conflict graph $C$ is 3-colorable. Let $L_2 = X_1 \cup X_2 \cup X_3$ be a partition into three independent sets of $C$.

Since $X_1,X_2,X_3$ partition $L_2$ and every edge of $E_{22} \cup E_{R_3L_2}$ has exactly one endpoint in $L_2$, some color class $X_i$ is incident with at least one third of the total weight of these edges.

Let $X := X_i$, and let $S_R$ consist of the edges of $E_{22} \cup E_{R_3L_2}$ incident with $X$. Then

which proves (6). Also let $S_L$ be the edges of $M_L$ incident with $X$.

Now move every vertex of $X$ from $L$ to $R$, and denote the resulting partition by $(L^*,R^*)$. Since $X$ is an independent set in the conflict graph $C$, no edge of $M_L$ has both endpoints in $X$. Hence the edges of $S_L$ become crossing, while the remaining edges of $M_L$ remain internal to $L^*$. Thus

Similarly, the crossing edges which become internal to $R^*$ are the edges of $S_R$, so

The cut $(L^*,R^*)$ contains every edge of $G$ except the edges of $(M_L \setminus S_L) \cup M_R \cup S_R$. Therefore

which is (4).

It remains to prove (5). We claim that the partition $(L^*,R^*)$ satisfies the hypotheses of Theorem 2.2. First, $G[L^*]$ is a collection of edges and isolated vertices, since $M_L \setminus S_L$ is a matching.

Next consider $G[R^*]$. Before moving $X$, every component of $G[R]$ was either an edge of $M_R$ or an isolated vertex. Since $X$ is independent in the conflict graph, no component of $G[R]$ is adjacent to two distinct vertices of $X$. Hence every component of $G[R^*]$ contains at most one vertex of $X$.

Moreover, a vertex $x \in X \subseteq L_2$ cannot have both of its neighbors in $R_2$, by Lemma 4.1. Among the two components of $G[R]$ adjacent to $x$, at most one is an edge of $M_R$. Therefore every component of $G[R^*]$ has order at most 4. Since $G$ has odd girth at least 7, every such component is bipartite.

Finally, let $C_R$ be a component of $G[R^*]$ and $C_L$ a component of $G[L^*]$. We have $|V(C_R \cup C_L)| \leq6$, which implies $G[C_R \cup C_L]$ is bipartite since $G$ has odd girth at least 7.

Applying Theorem 2.2 to $(L^*,R^*)$ gives

which is (5).

We now apply the same construction to $(L',R')$, with the roles of the two sides reversed. This time we choose the color class so that the edges of $M'_{R}$ that become crossing have large total weight. Each edge of $M'_{R}$ meets two of the three color classes, so some class captures at least $\frac{2}{3}w(M'_{R})$.

Proof. Consider the conflict graph $C'$ for $R'_2$. By Lemma 4.3, it is 3-colorable; let $R'_2=X_1\cup X_2\cup X_3$ be a partition into three independent sets.

Since the endpoints of every edge of $M'_{R}$ are adjacent in $C'$, they belong to distinct color classes. Thus every edge of $M'_{R}$ is incident with exactly two of the three color classes, so some color class $X_i$ is incident with edges of $M'_{R}$ of total weight at least $\frac{2}{3}w(M'_{R})$.

Set $X:=X_i$, and let $S'_{R}$ be the set of edges of $M'_{R}$ incident with $X$. Then

Let $S'_{L}$ be the set of edges of $E'_{22}\cup E'_{L_3R_2}$ incident with $X$.

Move every vertex of $X$ from $R'$ to $L'$ and denote the resulting partition by $(L^*,R^*)$. Then

The weight of the cut $(L^*,R^*)$ gives

proving (7).

As in the proof of Lemma 4.4, the independence of $X$ in $C'$ ensures that Theorem 2.2 applies, with the roles of $L^*$ and $R^*$ reversed. Therefore

proving (8).

The next bound exploits a different tradeoff; we can make every edge of $M_L$ crossing while retaining at least half the crossing weight incident with $L_2$. This is useful when substantial weight lies in $M_L$.

Proof. Starting from $(L, R)$, independently for each edge $uv \in M_L$, choose one of $u,v$ uniformly at random and move the chosen endpoint from $L$ to $R$. Let $(L^*, R^*)$ denote the resulting random partition.

Exactly one endpoint of every edge of $M_L$ is moved, so every edge of $M_L$ is crossing in $(L^*, R^*)$. Thus these edges contribute $w(M_L)$.

No endpoint of an edge in $E_{33}$ or $E_{L_3R_2}$ belongs to $L_2$. Therefore none of their endpoints is moved, and every such edge remains crossing. These classes contribute $w(E_{33}) + w(E_{L_3R_2})$.

Now let $e \in E_{22} \cup E_{R_3L_2}$. The edge $e$ remains crossing precisely when its $L_2$ endpoint is not chosen to move. The expected crossing weight contributed by these two edge classes is $\frac{1}{2}w(E_{22}) + \frac{1}{2}w(E_{R_3L_2})$.

Hence some realization of $(L^*, R^*)$ has crossing weight at least this expectation. Therefore

Now we combine the odd girth at least 7 bounds to get a universal bound for $\operatorname{mc}(G,w)$ in the odd girth at least 7 setting.

Odd Girth at Least Nine

A structural lemma of Berke and Szabó gives a natural partition to apply Theorem 2.2 for odd girth at least nine.

Proof. By Lemma 2.1, it suffices to consider the case that $G$ is cubic. By Lemma 4.7, there exists a partition $V(G)=I\cup B$ such that $I$ is an independent set and every component of $G[B]$ has order at most 6.

The partition $(I,B)$ satisfies the hypotheses of Theorem 2.2. First, $G[I]$ consists entirely of isolated vertices. Moreover, every component $C$ of $G[B]$ has at most 6 vertices. Since $G$ has odd girth at least 9, $C$ is bipartite. Finally, let $C$ be a component of $G[B]$ and let $v\in I$. Since $|V(C\cup\{v\})|\le7$, odd girth implies $G[C\cup\{v\}]$ is bipartite.

By Theorem 2.2,

On the other hand, the partition $(I,B)$ itself cuts every edge of $E(I,B)$, so

Taking $\frac{1}{5}$ times (15) and $\frac{4}{5}$ times (14) gives

□

Conclusion

Define $b(G)=\frac{\operatorname{mc}(G)}{|E(G)|}$ and $b(G,w)=\frac{\operatorname{mc}(G,w)}{w(G)}$. It is natural to ask whether $b(G,w)\ge b(G)$ for every triangle-free subcubic graph $G$ and every nonnegative edge weighting $w$. This is false even for cubic graphs. Consider the Wagner graph $W_8$, obtained from an 8-cycle by adding the four edges joining opposite vertices. This graph is triangle-free and cubic, and its maximum cut has size 10, so $b(W_8)=\frac{10}{12}=\frac{5}{6}$. However, $W_8$ contains a 5-cycle $C$. Assign weight $1/5$ to each edge of $C$ and weight zero to every other edge. Every cut misses at least one edge of $C$, and a cut crossing four of its edges extends to a cut of $W_8$. Hence $b(W_8,w)=\frac{4}{5}<\frac{5}{6}=b(W_8)$.

The Wagner graph example shows that weights can lower the maximum-cut ratio of an individual graph. However, the resulting ratio is still $4/5$, the unweighted bound for the entire triangle-free subcubic class. Thus the example leaves open whether allowing weights changes the worst-case ratio over an entire odd-girth class.

For each odd integer $g \ge5$, let $\mathcal{G}_g$ be the class of finite simple subcubic graphs with at least one edge and odd girth at least $g$, including bipartite graphs. Define

Uniform edge weights show that $b_g^{\mathrm{wt}} \le b_g^{\mathrm{unw}}$.

Our results give weighted lower bounds under stronger odd-girth assumptions, but determining the sharp bounds remains open even in the unweighted setting. As discussed in the introduction, Zhu [12] proved that every 2-connected triangle-free subcubic graph outside the seven exceptional graphs has maximum-cut ratio at least $17/21$. Since each exceptional graph contains a 5-cycle and maximum-cut sizes can only increase over bridges, this bound holds for every subcubic graph of odd girth at least seven. Together with Theorems 1.5 and 1.6,

Improving any of these lower bounds would be interesting. Finally, Theorem 2.2 suggests a structural approach to the weighted 4/5 conjecture.

One possible approach is to strengthen the component-order bound in Lemma 4.7, taking the odd girth into account.

An affirmative answer to Question 5.3 would imply the weighted 4/5 conjecture. Likewise, an affirmative answer to Question 5.4 or Question 5.5 would yield the weighted 4/5 conjecture for the corresponding odd-girth class.

Use of AI

The main mathematical ideas were developed solely by the author, including the structural analysis of maximum-cut partitions, the randomized cut construction underlying Theorem 2.2, and the use of odd-girth restrictions to obtain stronger bounds. ChatGPT-6 was used to simplify the component inequalities and compute the convex combinations in the proof of Theorem 1.5. It also assisted with improving LaTeX formatting and checking the manuscript for potential mathematical errors. The author reviewed and verified all AI-assisted material and takes full responsibility for the content of this paper.