\documentclass[11pt]{article}
\usepackage[a4paper,margin=26mm]{geometry}
\usepackage{amsmath,amssymb,amsthm,booktabs}
\usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue,citecolor=blue]{hyperref}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\AO}{a}
\newcommand{\rat}{\rho}
\title{Counterexamples to Three Conjectures of Ok on Tutte-Polynomial Deletion Ratios}
% IMPORTANT: Replace this placeholder with the correct human author name and affiliation.
\author{[Author name to be inserted]}
\date{October 2026}
\begin{document}
\maketitle
\begin{abstract}
We disprove Conjectures~7.2.1, 7.2.2, and 7.2.3 from Seongmin Ok's thesis \emph{Aspects of the Tutte polynomial}. Conjecture~7.2.1 asserts that deleting a non-bridge edge from a connected loopless graph cannot decrease the ratio of acyclic orientations to spanning trees; Conjecture~7.2.2 strengthens this to monotonicity of $T_{G-e}(x,2-x)/T_G(x,2-x)$ on $0\leq x\leq2$. Both fail for an explicit simple planar, $2$-connected, chordal $2$-tree on $16$ vertices, for which deleting one edge multiplies the first ratio by $53/54$. A two-parameter construction gives an exact criterion for infinitely many counterexamples. Conjecture~7.2.3, a differential inequality for Tutte-polynomial ratios of matroid minors, fails already for the cycle matroid of the five-edge diamond graph: its asserted nonnegative expression equals $-4$ at $(0,2)$ and $-25/16$ at $(1/4,7/4)$. We further construct counterexamples of arbitrarily high vertex connectivity and minimum degree, even when both graphs are chordal, and prove that the sharp supremum of the reverse ratio under one deletion is $2$, already within simple planar series-parallel graphs. These counterexamples do not disprove the Merino--Welsh inequalities.
\end{abstract}

\noindent\textbf{2020 Mathematics Subject Classification.} Primary 05C31; Secondary 05B35, 05C30, 05C40.\par
\noindent\textbf{Keywords.} Tutte polynomial, deletion monotonicity, acyclic orientations, spanning trees, graphic matroids, chordal graphs, counterexamples.

\section{The conjecture and a three-vertex counterexample}

Write $a(G)$ for the number of acyclic orientations of $G$, $\tau(G)$ for its number of spanning trees, and $\rho(G)=a(G)/\tau(G)$. Parallel edges are distinguished for spanning-tree enumeration and must have a common direction in any acyclic orientation. Ok's Conjecture~7.2.1, on printed page~92 of~\cite{Ok}, asserts that
\begin{equation}\label{eq:ok}
\rho(G)\leq \rho(G-e)
\end{equation}
whenever $G$ is connected and loopless and $e$ is not a bridge. The original formulation permits parallel edges. The constructions below also disprove its restriction to simple graphs.

For the shortest direct calculation, take three vertices $u,v,w$, a single edge $e=uv$, $r$ parallel edges between $u,w$, and $s$ parallel edges between $v,w$. Then
\[
a(G)=6,\qquad a(G-e)=4,\qquad
\tau(G)=rs+r+s,\qquad \tau(G-e)=rs.
\]
Consequently,~\eqref{eq:ok} fails precisely when $rs>2(r+s)$. Taking $(r,s)=(4,5)$ gives
\[
\rho(G)=\frac6{29}>\frac4{20}=\rho(G-e).
\]
Both graphs are loopless and bridgeless. This already refutes the stated conjecture. We now remove parallel edges entirely.

\section{A simple planar two-parameter family}

For integers $p,q\geq0$, let $G_{p,q}$ consist of a triangle $uvw$, a set $A=\{a_1,\ldots,a_p\}$ of additional vertices with neighborhood $\{u,w\}$, and a disjoint set $B=\{b_1,\ldots,b_q\}$ with neighborhood $\{v,w\}$. There are no other edges. Set $e=uv$ and $H_{p,q}=G_{p,q}-e$. Thus
\[
|V(G_{p,q})|=p+q+3,\qquad |E(G_{p,q})|=2p+2q+3.
\]
The graph $G_{p,q}$ is a $2$-tree: start with $uvw$ and add each further vertex onto an existing edge. In particular it is simple, planar, chordal, $2$-connected, and has treewidth $2$. It is therefore a series-parallel graph in the usual undirected, $K_4$-minor-free sense. If $p,q\geq1$, then $H_{p,q}$ is also bridgeless; it has the cutvertex $w$.

\begin{lemma}\label{lem:book}
Let $B_p$ be an edge $xy$ together with $p$ new vertices, each adjacent precisely to $x$ and $y$. Then
\[
a(B_p)=2\cdot3^p,\qquad \tau(B_p)=(p+2)2^{p-1}.
\]
The spanning-tree formula at $p=0$ is interpreted as $2\cdot2^{-1}=1$.
\end{lemma}
\begin{proof}
Fix a direction of $xy$. Each added vertex has exactly three allowable orientation patterns on its two incident edges; the fourth pattern closes a directed triangle. None of the three allowable patterns creates a longer directed cycle, since a directed passage through the new vertex between $x$ and $y$ follows the existing direction of $xy$. Thus every added vertex contributes a factor $3$.

For spanning trees containing $xy$, each new vertex chooses exactly one of its two incident edges, giving $2^p$ trees. For spanning trees not containing $xy$, exactly one of the $p$ added vertices uses both its edges, and each other added vertex chooses one edge. This gives $p2^{p-1}$ trees for $p\geq1$. Adding the two cases proves the formula; $p=0$ is immediate.
\end{proof}

\begin{theorem}\label{thm:planar}
Put $P=p+q$. The following exact formulas hold:
\begin{align*}
a(H_{p,q})&=4\cdot3^P,&
a(G_{p,q})&=6\cdot3^P,\\
\tau(H_{p,q})&=2^{P-2}(p+2)(q+2),&
\tau(G_{p,q})&=2^{P-2}(pq+4p+4q+12).
\end{align*}
In particular,
\begin{equation}\label{eq:gamma-book}
\frac{\rho(G_{p,q})}{\rho(H_{p,q})}
=\frac{3(p+2)(q+2)}{2(pq+4p+4q+12)},
\end{equation}
and this ratio exceeds $1$ if and only if
\begin{equation}\label{eq:condition}
(p-2)(q-2)>16.
\end{equation}
\end{theorem}
\begin{proof}
The orientation formulas follow by starting from the triangle, respectively the two-edge path $u,w,v$, and applying the factor-$3$ extension in Lemma~\ref{lem:book} once for each added vertex.

The graph $H_{p,q}$ is the one-vertex union of $B_p$ and $B_q$, so its spanning-tree count is the product of the two book counts. In $G_{p,q}/e$, the identified vertex $u=v$ and $w$ are joined by two parallel edges, and all $P$ remaining vertices have precisely these two neighbors. A spanning tree using one of the two parallel edges can choose it in two ways and then has $2^P$ choices at the remaining vertices. A spanning tree using neither parallel edge must connect the two central vertices through exactly one of the $P$ other vertices, giving $P2^{P-1}$ choices. Hence
\[
\tau(G_{p,q}/e)=(P+4)2^{P-1}.
\]
For $P=0$, this expression equals $2$, the direct count. Deletion--contraction gives
\[
\tau(G_{p,q})=\tau(H_{p,q})+\tau(G_{p,q}/e)
=2^{P-2}\bigl[(p+2)(q+2)+2(P+4)\bigr].
\]
Substitution proves~\eqref{eq:gamma-book}. Its numerator minus its denominator is
\[
3(p+2)(q+2)-2(pq+4p+4q+12)
=pq-2p-2q-12=(p-2)(q-2)-16,
\]
which proves~\eqref{eq:condition}.
\end{proof}

Take $p=6$ and $q=7$. Exact values are as follows; contraction retains the parallel edges it creates.
\begin{center}
\begin{tabular}{lrrrr}
\toprule
Graph & Vertices & Edges & $a$ & $\tau$\\
\midrule
$G=G_{6,7}$ &16&29&9,565,938&217,088\\
$H=G-e$ &16&28&6,377,292&147,456\\
$G/e$ &15&28&3,188,646&69,632\\
\bottomrule
\end{tabular}
\end{center}
In particular,
\begin{equation}\label{eq:54-53}
\frac{\rho(G)}{\rho(H)}=\frac{54}{53}>1,
\qquad
a(G)\tau(H)-a(H)\tau(G)=26\,121\,388\,032>0.
\end{equation}
Thus deleting $e$ decreases $\rho$ to exactly $53/54$ of its previous value. The parameters $p=6,q=7$ minimize $p+q$ within this family: for $P\leq12$,
\[
(p-2)(q-2)\leq\frac{(P-4)^2}{4}\leq16.
\]
This is not a claim of minimality among all graphs. Taking $p=q\geq7$ gives a particularly symmetric infinite family.

\section{Arbitrarily high connectivity and minimum degree}

The cutvertex of $H_{p,q}$ is not essential to the failure.

\begin{theorem}\label{thm:connectivity}
Let $k\geq1$, $r,s\geq k+2$, and let $H$ be the union of two cliques $K_r$ and $K_s$ whose intersection is precisely a clique $S\cong K_k$. Choose $u\in K_r-S$ and $v\in K_s-S$ and set $G=H+uv$. Then
\begin{equation}\label{eq:clique-ratios}
\frac{a(G)}{a(H)}=\frac{k+2}{k+1},\qquad
\frac{\tau(G)}{\tau(H)}
=1+\frac{k+1}{k}\left(\frac1r+\frac1s\right).
\end{equation}
Therefore $\rho(G)>\rho(H)$ exactly when
\begin{equation}\label{eq:clique-condition}
krs>(k+1)^2(r+s).
\end{equation}
Both graphs are chordal, with $\kappa(H)=k$ and $\kappa(G)=k+1$. Their minimum degrees are $\min\{r-1,s-1\}$.
\end{theorem}
\begin{proof}
An acyclic orientation of a clique is a total order. Fixing an order on $S$, the orientations on the two larger cliques are independent and compatible precisely when both restrict to that order. Thus $a(H)=r!s!/k!$.

For a fixed order on $S$, each of $u$ and $v$ falls uniformly into one of the $k+1$ gaps in that order, and these two choices are independent. They are incomparable in the directed reachability order of $H$ exactly when they occupy the same gap. If their gaps differ, exactly one direction of $uv$ is acyclic; if their gaps coincide, both directions are acyclic. Therefore
\[
a(G)=a(H)\left(1+\frac1{k+1}\right).
\]

For a unit-resistance graph, the matrix-tree theorem and the rank-one determinant identity give
\[
\frac{\tau(H+uv)}{\tau(H)}=1+R_H(u,v),
\]
where $R_H$ is effective resistance. To compute it here, send a unit current from $u$ to $v$. Permutations of $S$ preserve the network and the source and sink, so every vertex of $S$ has the same potential. The two sides consequently act in series through an equipotential $S$.

In the $K_r$ side, short $S$ to a single terminal. If $u$ has potential $V$ relative to $S$, each of the $r-k-1$ other vertices outside $S\cup\{u\}$ has potential $V/(k+1)$. The current out of $u$ is
\[
kV+(r-k-1)\frac{kV}{k+1}=\frac{kr}{k+1}V.
\]
The resistance of this side is therefore $(k+1)/(kr)$. The other side contributes $(k+1)/(ks)$, proving~\eqref{eq:clique-ratios}. Cross multiplication gives~\eqref{eq:clique-condition}.

The graph $H$ is a clique sum along $S$. For $G$, its maximal cliques have a clique-tree ordering
\[
K_r\;---\;(S\cup\{u,v\})\;---\;K_s,
\]
with clique intersections $S\cup\{u\}$ and $S\cup\{v\}$. This proves chordality. Removing $S$ disconnects $H$. Any deletion of fewer than $k$ vertices leaves a common vertex joining its two cliques. Hence $\kappa(H)=k$.

Any deletion of at most $k$ vertices from $G$ either leaves a vertex of $S$, or deletes exactly $S$ and leaves the edge $uv$ joining the two sides. Conversely, deleting $S\cup\{u\}$ disconnects $G$, since each side has at least two vertices outside $S$. This proves $\kappa(G)=k+1$. The non-distinguished private vertices have degrees $r-1$ and $s-1$ and all other degrees are no smaller, proving the minimum-degree claim.
\end{proof}

For every $k\geq1$, the choice $r=s=2k+7$ satisfies~\eqref{eq:clique-condition}, since
\[
k(2k+7)-2(k+1)^2=3k-2>0.
\]
Thus arbitrary prescribed lower bounds on both connectivity and minimum degree are compatible with counterexamples, including when both $G$ and $G-e$ must be chordal. A smaller concrete example with $G-e$ already $2$-connected is $k=2$, $r=s=10$. It has $18$ vertices and satisfies $\rho(G)/\rho(G-e)=40/39$.

For completeness, writing $n=r+s-k$, the base spanning-tree count is
\[
\tau(H)=k n^{k-1}r^{r-k-1}s^{s-k-1}.
\]
Indeed the Laplacian eigenvalues are $0$, $k$, $n$ with multiplicity $k$, $r$ with multiplicity $r-k-1$, and $s$ with multiplicity $s-k-1$. Their nonzero product divided by $n$ gives the displayed formula.

\section{The sharp reverse factor is two}

\begin{theorem}\label{thm:sharp}
For any connected loopless graph $G$ and non-bridge edge $e$,
\[
\frac{\rho(G)}{\rho(G-e)}<2.
\]
The supremum $2$ is attained as a limit of simple planar series-parallel examples.
\end{theorem}
\begin{proof}
Every acyclic orientation of $G-e$ has at most two extensions across $e$, so $a(G)\leq2a(G-e)$. Also $\tau(G)>\tau(G-e)$, because some spanning tree contains the non-loop edge $e$. These two observations give the strict bound.

For sharpness, fix integers $\ell\geq2$ and $t\geq1$. Start from an $\ell$-edge path. On each path edge add $t$ new vertices adjacent precisely to its endpoints, retaining the original edge. Call the resulting graph $H_{\ell,t}$, and add the edge $e$ joining the two endpoints of the original path to obtain $G_{\ell,t}$.

Each added vertex contributes a factor $3$ to acyclic orientations. The base path has $2^\ell$ acyclic orientations, and the base $(\ell+1)$-cycle has $2^{\ell+1}-2$. Hence
\[
\frac{a(G_{\ell,t})}{a(H_{\ell,t})}=2-2^{1-\ell}.
\]
The $\ell$ book blocks are in series. Each block has effective resistance $2/(t+2)$ between its spine endpoints, so
\[
\frac{\tau(G_{\ell,t})}{\tau(H_{\ell,t})}
=1+\frac{2\ell}{t+2}.
\]
Consequently,
\begin{equation}\label{eq:sharp-family}
\frac{\rho(G_{\ell,t})}{\rho(H_{\ell,t})}
=\frac{2-2^{1-\ell}}{1+2\ell/(t+2)}.
\end{equation}
Letting $t\to\infty$ for a fixed $\ell$, and then $\ell\to\infty$, gives the limit $2$; alternatively take $t=\ell^3$ and let $\ell\to\infty$. These graphs are simple and planar. The base cycle has treewidth $2$, and adding a vertex adjacent to the endpoints of an existing edge preserves treewidth at most $2$. Thus all graphs in the sequence are series-parallel. For all sufficiently large parameters,~\eqref{eq:sharp-family} exceeds $1$.
\end{proof}

\section{Direct counterexamples to Conjectures 7.2.2 and 7.2.3}

Ok's Conjecture~7.2.2 (printed p.~93 of~\cite{Ok}) states that, for every connected loopless graph $G$ and non-bridge edge $e$,
\[
f_{G,e}(x):=\frac{T_{G-e}(x,2-x)}{T_G(x,2-x)}
\]
is nondecreasing for $0\leq x\leq2$. For the simple planar graph $G_{6,7}$ of Theorem~\ref{thm:planar}, the evaluations above yield
\[
f_{G,e}(1)=\frac{\tau(G-e)}{\tau(G)}=\frac{36}{53}
>\frac23=\frac{a(G-e)}{a(G)}=f_{G,e}(2),
\]
so this conjecture is false even for simple planar $2$-connected graphs.

Conjecture~7.2.3 in~\cite{Ok}, also on printed p.~93, is a universal matroid statement. For an element $e$ of a matroid $M$ it requires
\begin{equation}\label{eq:derivative-conjecture}
W_{M,e}(x,y):=
T_{M/e}(x,y)\,\partial_x T_{M\setminus e}(x,y)
-\partial_x T_{M/e}(x,y)\,T_{M\setminus e}(x,y)\geq0
\end{equation}
at every point of the line segment $x,y\geq0$, $x+y=2$. The following independent four-vertex example disproves this directly, without appealing to an implication between conjectures.

\begin{proposition}\label{prop:diamond}
Let $D$ be the diamond graph with vertex set $\{u,v,a,b\}$ and edge set
\[
\{uv,ua,va,ub,vb\},
\]
so $D\cong K_4-ab$ is two triangles sharing the edge $e=uv$. For its cycle matroid $M=M(D)$, the expression in~\eqref{eq:derivative-conjecture} satisfies
\[
W_{M,e}(0,2)=-4,\qquad
W_{M,e}\bigl(\tfrac14,\tfrac74\bigr)=-\tfrac{25}{16}.
\]
In particular, Conjecture~7.2.3 is false even for the cycle matroid of a simple planar graph, and fails at an interior point of the stipulated segment.
\end{proposition}
\begin{proof}
Deleting the shared edge from $D$ gives the four-cycle $C_4$, whereas contracting it gives the one-vertex union of two two-edge parallel bundles. Hence
\[
T_{M\setminus e}(x,y)=x^3+x^2+x+y,
\qquad T_{M/e}(x,y)=(x+y)^2.
\]
Differentiating and factoring gives
\begin{align*}
W_{M,e}(x,y)
&=(x+y)^2(3x^2+2x+1)-2(x+y)(x^3+x^2+x+y)\\
&=(x+1)(x+y)(x^2+3xy-x-y).
\end{align*}
Substituting $(x,y)=(0,2)$ and $(x,y)=(1/4,7/4)$ yields the two negative values.
\end{proof}

We emphasize the scope of these statements. Conjectures~7.2.1--7.2.3 are all disproved as written. The counterexamples do not, merely by their existence, refute the separate threshold assertions in Ok's Conjecture~7.2.4, the coefficientwise positivity question in Conjecture~7.2.5, or the graph Merino--Welsh inequality. In particular, no stronger statement about these other problems is asserted here.

\section{Exact verification and scope}

The numerical data for the $16$-vertex graph were checked by a separate standard-library Python implementation, using general counting algorithms rather than the special formulas proved here. For any graph $F$, the number of acyclic orientations can be computed by inclusion--exclusion over nonempty independent sets of possible sources:
\[
a(F)=\sum_{\substack{\varnothing\ne I\subseteq V(F)\\I\text{ independent}}}
(-1)^{|I|+1}a(F-I),\qquad a(\varnothing)=1.
\]
Spanning trees were computed as a Laplacian cofactor by exact Bareiss elimination, retaining edge multiplicities after contraction. In particular, both evaluations of the main example and its deletion--contraction identities were checked with integer arithmetic. The derivative example can be checked independently from the five-edge graph by the defining subset expansion for the Tutte polynomial. All displayed results have mathematical proofs not depending on these programs; the verification scripts are separate reproducibility material and are not required to compile this manuscript.

The $16$-vertex order is the minimum \emph{within the specified two-parameter book family}, not a proven global minimum for simple graphs. No claim of priority over any as-yet-unidentified prior counterexamples is made.

\begin{thebibliography}{9}
\bibitem{Ok} Seongmin Ok, \emph{Aspects of the Tutte polynomial}, Ph.D. thesis, Technical University of Denmark, DTU Compute PHD-2015, no.~384, written 2015, publication record 2016. Chapter~7, especially Conjectures~7.2.1--7.2.3, printed pp.~92--94.\newline
\url{https://backend.orbit.dtu.dk/ws/portalfiles/portal/123426012/phd384_Ok_S.pdf}
\end{thebibliography}
\end{document}