\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage{booktabs}
\geometry{margin=1in}

\title{Must a minimum $4$CT counterexample have a separating
$n$-cycle with $n$ even and $n \ge 6$?}
\author{}
\date{}

\newtheorem*{thm}{Theorem}
\newtheorem*{lem}{Lemma}
\newtheorem*{prop}{Proposition}
\newtheorem*{conj}{Conjecture}
\newtheorem*{rem}{Remark}

\begin{document}
\maketitle

\section*{The question}

\paragraph{Statement.}  Let $G$ be a hypothetical minimum
$4$-colour counterexample (a minimum planar triangulation
requiring $\ge 5$ colours).  Must $G$ contain a separating
$n$-cycle with $n$ \emph{even} and $n \ge 6$?

\paragraph{Short answer.}  I do not know of a proof either way.
The question is subtle: a parity computation (below) shows that
cuts in the cubic dual $G^*$ have a definite parity tied to the
side sizes, but I do not see this parity forcing the existence of
even-length separating cycles.

\section*{Parity computation in the cubic dual}

Let $G$ be a planar triangulation and $G^*$ its cubic planar dual.
$G$ has $V$ vertices, $3V - 6$ edges, $2V - 4$ faces; $G^*$ has
$2V - 4$ vertices, $3V - 6$ edges, $V$ faces.  In particular,
$|V(G^*)| = 2V - 4$ is \emph{always even}.

\begin{lem}[Cut size parity in cubic graphs]
\label{lem:cut-parity}
Let $G^*$ be a cubic graph and let $C$ be an edge cut separating
$V(G^*)$ into sides $S$ and $T = V(G^*) \setminus S$.  Then
\[
|C| \equiv |S| \equiv |T| \pmod{2}.
\]
\end{lem}

\begin{proof}
Counting degree on side $S$: $3|S| = 2 e_S + |C|$, where $e_S$ is
the number of edges with both endpoints in $S$.  Hence
$|C| = 3|S| - 2e_S \equiv |S| \pmod{2}$.  Since
$|S| + |T| = |V(G^*)|$ is even, $|S| \equiv |T| \pmod 2$.
\end{proof}

\paragraph{Translating to primal cycles.}  Via the $G \leftrightarrow
G^*$ duality, an $n$-cycle in $G$ corresponds to an $n$-edge cut in
$G^*$.  Lemma~\ref{lem:cut-parity} says: an \emph{even} $n$-cycle
in $G$ ($n \ge 6$) corresponds to a $G^*$ cut with both sides
having an \emph{even} number of vertices.  An \emph{odd}
$n$-cycle in $G$ ($n \ge 7$) corresponds to both sides having an
\emph{odd} number of vertices.

\section*{What Birkhoff gives us}

For a minimum $4$CT counterexample $G$:
\begin{itemize}
\item $G$ is internally $6$-connected (no separating $3$-cycle, no
      separating $4$-cycle, no separating $5$-cycle with $\ge 2$
      vertices on each side).
\item Equivalently in $G^*$: cyclic edge connectivity $\ge 6$.
\end{itemize}

So all sufficiently small cuts in $G^*$ are excluded.  The smallest
non-trivial cuts can be $6$-edge ($n = 6$, even) or $7$-edge
($n = 7$, odd), and Birkhoff alone permits both.

\section*{A potential ``no'' --- can $G^*$ have only odd cuts $\ge 7$?}

In principle, the minimum non-trivial cut could be $7$ (and all
non-trivial cuts could be odd-length).  In this case the
minimum primal separating cycle has length $7$ (odd), and the
question's answer is ``no.''

\paragraph{Is this realisable?}  We need a planar cubic graph $G^*$
satisfying:
\begin{itemize}
\item cyclic edge connectivity $\ge 7$;
\item all non-trivial cyclic edge cuts have odd size.
\end{itemize}

Lemma~\ref{lem:cut-parity} gives a constraint: if a $G^*$ has
\emph{any} cut at all of size $\ge 6$, its parity is fixed by side
size.  For ``all cuts odd'' to hold, no even-sized cut would
separate.  In a cubic graph this corresponds to the side sizes
being \emph{odd}.  Since $|V(G^*)|$ is even (for any planar
triangulation dual), the sides $(|S|, |V(G^*)| - |S|)$ have
matching parity --- both even or both odd.  ``All cuts odd''
means ``all cyclic separations have odd side sizes,'' which is
possible in principle.

\paragraph{However:} I don't know of a planar cubic graph that has
\emph{only} odd cyclic cuts.  The known internally $6$-connected
examples (icosahedron's dual = dodecahedron, etc.) all have
many even cuts of size $6$ as well as odd cuts.

\section*{What the maximal-planar constraint forces}

Maximal planar (= triangulation) gives strong constraints:
$E = 3V - 6$, $F = 2V - 4$, $\sum \deg = 6V - 12$.  Average degree
approaches $6$ from below.  Internally $6$-connected forces min
degree $\ge 5$.

\paragraph{Forced $12$ degree-$5$ vertices.}  If all degrees are in
$\{5, 6\}$:
\[
5 n_5 + 6 n_6 = 6V - 12, \quad n_5 + n_6 = V \implies n_5 = 12.
\]
So exactly $12$ degree-$5$ vertices, with the remaining $V - 12$
of degree $6$.  For $V > 12$, at least some degree-$5$ vertex has a
degree-$6$ link neighbour.

\paragraph{Second-link length.}  For vertex $v$ of degree $d$ in a
triangulation, the second link (cycle of vertices at distance
exactly $2$) has length
\[
L_2(v) = d + \sum_{u \in \mathrm{link}(v)} (\deg u - 5).
\]
(Each link vertex contributes one ``shared'' boundary vertex with
each link-cycle neighbour, plus $\deg u - 5$ private boundary
vertices inside $u$'s fan.)  For the icosahedron ($d = 5$, all
link degrees $5$): $L_2 = 5$.

\paragraph{Second-link length does \emph{not} pin down min cyclic
cut.}  The pentakis dodecahedron ($V = 32$): every degree-$5$
vertex has all $5$ link vertices of degree $6$, so $L_2 = 5 + 5 =
10$ around degree-$5$ vertices.  Around degree-$6$ vertices,
$L_2 = 6 + 0 \cdot 2 + 1 \cdot 4 = 10$.  So no second-link
separator has length $6$.

\emph{But} the pentakis dodecahedron's dual (Buckminsterfullerene
graph) \emph{does} have $6$-edge cyclic cuts --- they arise as
separations \emph{not} surrounding a single vertex.  So
second-link length is just one source of cyclic cuts; longer
constructions can yield smaller cuts.

\paragraph{Conclusion of this section.}  The maximal-planar
constraint forces some structural relations but does not pin down
the minimum non-facial cyclic cut to any specific value.  A
minimum $4$CT counterexample could in principle have any min cut
size $\ge 6$.

\section*{What I can conclude}

\begin{itemize}
\item \textbf{Parity is determined by side size}
      (Lemma~\ref{lem:cut-parity}).  Even $n$-cycle separators in $G$
      correspond to even-sided cuts in $G^*$.
\item \textbf{Birkhoff doesn't rule out odd cuts.}  Minimum
      non-trivial cyclic cut in $G^*$ could in principle be of any
      size $\ge 6$.
\item \textbf{No known proof that even $n \ge 6$ separators must
      exist} in min $4$CT counterexamples.
\item \textbf{Empirically}, in all tested internally $6$-connected
      planar triangulations (icosahedron, pentakis dodecahedron,
      Holton--McKay duals), even $6$-cycle separators with
      both sides $\ge 2$ vertices exist in abundance.
\end{itemize}

\section*{Conjecture}

\begin{conj}
Every internally $6$-connected planar triangulation $G$ with
$|V(G)| \ge 12$ has a separating $n$-cycle with $n$ even and
$n \ge 6$.
\end{conj}

Equivalently: every planar cubic graph with cyclic edge
connectivity $\ge 6$ and $|V| \ge 20$ has a cyclic edge cut of
size $6$.

This conjecture seems plausible based on the second-link
heuristic, but I don't have a proof.  A planar cubic graph that
violates it would be a structural curiosity worth a name --- a
``cyclically $7$-edge-connected planar cubic graph'' --- and I do
not know an example.

\paragraph{Relevance to the cut-tire framework.}  If the
conjecture holds, our cut-tire framework's domain assumption (=
cyclic edge connectivity exactly $6$ in $G^*$) is automatically
satisfied by every minimum $4$CT counterexample.  If it doesn't
hold, we'd need to either prove that the counterexample is not
of the violating type, or extend the framework to higher-size
cuts.

\section*{Could the minimum non-trivial cyclic cut be $8$?}

\paragraph{Yes, in principle.}  Birkhoff gives $\ge 6$; nothing in
the condition pins the value to $6$.  A planar cubic $G^*$ with
non-facial cyclic edge connectivity \emph{exactly $8$} would have:
\begin{itemize}
\item No non-facial cyclic cut of size $6$ (= no separating
      $6$-cycle in $G$ with $\ge 2$ vertices each side).
\item No non-facial cyclic cut of size $7$ (= no separating
      $7$-cycle in $G$ with $\ge 2$ vertices each side).
\item Some non-facial cyclic cut of size $8$.
\end{itemize}

By the cut-parity lemma, a size-$8$ cut would have even-sized
sides.  Size-$7$ cuts would have odd-sized sides; for such cuts
to not exist non-facially, the graph would need a structural
parity barrier or just lack any odd-cardinality separations.

\paragraph{What would force this?}  Looking at the second-link
heuristic: if every vertex's link contains only vertices of degree
$\ge 6$ rather than the icosahedron-tight degree $5$, the
second-link length jumps to $\ge 5 + 5 \cdot 1 = 10$.  Such graphs
exist (denser triangulations); whether such a graph is also a
minimum $4$CT counterexample (= class-2 cubic dual + planar +
internally $6$-connected) is unknown.

\paragraph{The framework adapts.}  Even if the minimum non-trivial
cyclic cut is $8$ (or some other value $> 6$), the cut-tire chain
DP doesn't structurally depend on cut size $= 6$.  The same
constructions (cut tires, boundary cut tire $T_\partial$, chain DP
via shared edges) apply to $8$-edge cuts with minor parameter
changes.  What \emph{does} change: per-tire enumeration size
scales with cut size, and the per-tire half (Prop 1.13) was proved
specifically for spoke-only cut tires with simple-cycle face
boundaries --- it would need re-examining for larger structures.

\paragraph{Bottom line.}  The minimum non-trivial cyclic cut size
for a hypothetical $4$CT counterexample is one of
$\{6, 7, 8, 9, \dots\}$, and Birkhoff alone doesn't pin it down.
The framework's natural domain is whichever value it happens to
take, with $6$ being the simplest case to enumerate and study.

\end{document}
