\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage{booktabs}
\usepackage{tikz}
\usetikzlibrary{backgrounds,decorations.pathreplacing}
\geometry{margin=1in}

\title{The boundary cut tire $T_\partial$: closing the coverage gap}
\author{}
\date{}

\newtheorem*{defn}{Definition}
\newtheorem*{prop}{Proposition}
\newtheorem*{lem}{Lemma}
\newtheorem*{rem}{Remark}

\begin{document}
\maketitle

\section*{Motivation}

The high-side cut tire forest (\texttt{cut\_tire\_tree\_structure.tex})
omits the low-side face of $H_1$ --- the unique face containing the
pendants of $G'_i$.  This omission is essential to prove the
forest's tree structure (low-side faces span multiple parent faces
of $H_{d-1}$, violating the uniqueness step in the proof).

\paragraph{The coverage gap.}  Empirically
(\texttt{chain\_dp\_joint.py} on the dodecahedron, cut $\#0$, side
$0$): when $|S_i|$ is small, $H_1$ on side $i$ can be a
\emph{tree} (no cycles).  Its unique face is forced to be low-side
(contains pendants), so the high-side forest is \emph{empty}.  The
chain DP, projecting through roots that don't exist, gives
$\mathcal{R}_i = \emptyset$ --- but $G$ may still be
$3$-edge-colourable, with non-empty $\mathcal{R}_i$.

\paragraph{Resolution.}  Introduce the \emph{boundary cut tire}
$T_\partial^{(i)}$ on each side $i$, representing the low-side face
of $H_1$ together with the depth-$0$ pendants.  It is not a child of
any other tire (it sits at the framework's outer boundary), but the
chain DP can use it as a special root that interfaces between the
high-side forest interior and the cut.

\section*{Definition}

\paragraph{Setup.}  Fix a side $i$ of a $6$-edge cut of $G$.  Let
$G'_i = (G[S_i] \cup \text{pendants})$ with edge depths assigned by
BFS from pendants (depth $0$).  $H_d = $ the subgraph of $G'_i$
spanned by depth-$d$ edges.

\paragraph{The low-side face of $H_1$.}  By the level-set lemma,
each face of $H_1$ is entirely low-side (interior contains only
depth-$0$ edges = pendants) or entirely high-side (interior
contains only depth-$\ge 2$ edges).  There is exactly one low-side
face: the unique face whose interior contains the pendants.  Call
it $f_\partial^{(i)}$.

\begin{defn}[Boundary cut tire $T_\partial^{(i)}$]
The \emph{boundary cut tire} on side $i$ is the labelled multigraph
$T_\partial^{(i)}$ obtained from:
\begin{itemize}
\item The boundary walk of $f_\partial^{(i)}$ in $H_1$ (the edges
      of $H_1$ on the boundary of the low-side face), with each
      depth-$1$ edge contributing one cycle edge.
\item For each boundary vertex $v$ of $f_\partial^{(i)}$ with
      $\deg_{H_1}(v) = 2$:
      \begin{itemize}
      \item The pendant edge at $v$ (= depth-$0$ cut edge), labelled
            ``OUT.''
      \item If the third edge at $v$ has depth $2$ (= edge of $H_2$
            in an adjacent high-side $H_1$ face), one labelled
            ``IN'' pendant.
      \end{itemize}
\end{itemize}
\end{defn}

\paragraph{Picture.}  A thick-side example with $H_1$ a hexagonal
cycle in $G'_i$: the low-side face $f_\partial$ is the outer
(unbounded) region containing $3$ pendants (depth $0$); the
adjacent high-side face is inside the hexagon, containing depth-$2$
edges.

\begin{center}
\begin{tikzpicture}[scale=1.6]
  \def\R{1.6}
  \foreach \i in {0,...,5} {
    \pgfmathsetmacro{\ang}{60*\i + 90}
    \node[circle, fill=black, inner sep=1.3pt] (v\i) at (\ang:\R) {};
  }
  \begin{scope}[on background layer]
    \fill[red!8] (-3.2,-2.4) rectangle (3.2,2.4);
    \fill[green!8]
      (90:\R) -- (150:\R) -- (210:\R) -- (270:\R) --
      (330:\R) -- (30:\R) -- cycle;
  \end{scope}
  \foreach \i in {0,...,5} {
    \pgfmathtruncatemacro{\j}{mod(\i+1,6)}
    \draw[blue, very thick] (v\i) -- (v\j);
  }
  \foreach \i in {0,2,4} {
    \pgfmathsetmacro{\ang}{60*\i + 90}
    \coordinate (p\i) at (\ang:\R+0.85);
    \draw[red, thick, dashed] (v\i) -- (p\i);
    \node[circle, draw=red, fill=white, inner sep=1.2pt] at (p\i) {};
  }
  \foreach \i in {1,3,5} {
    \pgfmathsetmacro{\ang}{60*\i + 90}
    \coordinate (q\i) at (\ang:\R-0.7);
    \draw[green!55!black, thick, dashed] (v\i) -- (q\i);
    \node[circle, fill=green!55!black, inner sep=1.2pt] at (q\i) {};
  }
  \node[blue] at (0, \R+0.35) {\small cycle of $T_\partial$ ($= \partial f_\partial$, depth $1$)};
  \node[red] at (2.95, 1.55) {\small OUT pendants};
  \node[red] at (2.95, 1.25) {\small (depth $0$, cut)};
  \node[green!55!black] at (0, -0.05) {\small IN pendants (depth $2$)};
  \node at (-2.55, -1.95) {\small low-side face $f_\partial$};
  \node at (2.4, -2.05) {\small (high-side interior)};
\end{tikzpicture}
\end{center}

The cycle of $T_\partial$ is the hexagon (blue, depth $1$); pendants
fall in two classes: OUT (red, dashed, going into the low-side
face) attach to the cut, and IN (green, dashed, going into the
adjacent high-side region) attach to depth-$2$ edges shared with
$T_2^{(f')}$ tires.

\paragraph{What $T_\partial$ looks like in special cases.}
\begin{itemize}
\item \emph{Side with thick BFS:} $H_1$ has multiple faces, one
      low-side ($f_\partial$) and one or more high-side.
      $T_\partial$ has cycle = boundary of $f_\partial$ + OUT
      pendants (= cut edges incident to $f_\partial$'s boundary)
      + IN pendants (= depth-$2$ edges in adjacent high-side faces).
\item \emph{Side with thin BFS} (e.g.\ $H_1$ a tree): The unique
      $H_1$ face is $f_\partial$.  $T_\partial$ has cycle =
      boundary walk of this single face (each $H_1$ edge contributes
      \emph{two} cycle-edge traversals, since the walk goes around
      each edge on both sides) + OUT pendants at $V_{\deg = 2}$.
      No IN pendants (no depth-$2$ edges exist).
\end{itemize}

\begin{center}
\begin{tikzpicture}[scale=1.5]
  \node[circle, fill=black, inner sep=1.3pt] (a) at (-1.5, 0) {};
  \node[circle, fill=black, inner sep=1.3pt] (b) at (-0.5, 0) {};
  \node[circle, fill=black, inner sep=1.3pt] (c) at ( 0.5, 0) {};
  \node[circle, fill=black, inner sep=1.3pt] (d) at ( 1.5, 0) {};
  \begin{scope}[on background layer]
    \fill[red!8] (-3.2,-1.4) rectangle (3.2,1.4);
  \end{scope}
  \draw[blue, very thick] (a) -- (b) -- (c) -- (d);
  \draw[blue, thick, decorate, decoration={brace, amplitude=4pt, raise=8pt}]
    (a) -- (d) node[midway, above=12pt, blue] {\small $H_1$ (a tree, 3 edges)};
  \coordinate (pb) at (-0.5, -0.9);
  \coordinate (pc) at ( 0.5, -0.9);
  \draw[red, thick, dashed] (b) -- (pb);
  \draw[red, thick, dashed] (c) -- (pc);
  \node[circle, draw=red, fill=white, inner sep=1.2pt] at (pb) {};
  \node[circle, draw=red, fill=white, inner sep=1.2pt] at (pc) {};
  \node[red] at (-2.2, -0.5) {\small OUT pendants};
  \node[red] at (-2.2, -0.8) {\small (depth $0$)};
  \node at (2.5, 0.4) {\small low-side $f_\partial$};
  \node at (2.5, 0.1) {\small (the only face)};
  \draw[->, gray, thick]
    (-1.5, 0.5) .. controls (-2.2, 1.2) and (2.2, 1.2) .. (1.5, 0.5);
  \draw[->, gray, thick]
    (1.5, -0.5) .. controls (2.2, -1.2) and (-2.2, -1.2) .. (-1.5, -0.5);
  \node[gray] at (0, 1.05) {\small boundary walk traverses each edge twice};
\end{tikzpicture}
\end{center}

In the thin case (e.g.\ dodecahedron cut $\#0$ side $0$ with
$|S_0| = 4$), the boundary walk of the single face has length $6$
(each of $3$ $H_1$ edges visited twice), and OUT pendants attach at
the two $V_{\deg = 2}$ vertices.

\section*{High-side cut tires alongside $T_\partial$}

A high-side cut tire $T_d^{(f)}$ at depth $d$ has the same
structural shape as $T_\partial$:
\begin{itemize}
\item Cycle = depth-$d$ edges in $\partial f$ ($H_d$ edges).
\item OUT spokes = depth-$(d-1)$ edges at boundary vertices
      (pointing outward, toward parent).
\item IN spokes = depth-$(d+1)$ edges at boundary vertices
      (pointing inward, toward children).
\end{itemize}

\begin{center}
\begin{tikzpicture}[scale=1.3]
  \def\Rout{2.1}
  \def\Rin{1.0}
  % Outer hexagon = T_∂ cycle (depth 1)
  \foreach \i in {0,...,5} {
    \pgfmathsetmacro{\ang}{60*\i + 90}
    \node[circle, fill=black, inner sep=1.2pt] (vo\i) at (\ang:\Rout) {};
  }
  % Inner triangle = T_2^{(f')} cycle (depth 2)
  \foreach \i in {0,1,2} {
    \pgfmathsetmacro{\ang}{120*\i + 90}
    \node[circle, fill=black, inner sep=1.2pt] (vi\i) at (\ang:\Rin) {};
  }
  % Outer cycle edges (T_∂)
  \foreach \i in {0,...,5} {
    \pgfmathtruncatemacro{\j}{mod(\i+1,6)}
    \draw[blue, very thick] (vo\i) -- (vo\j);
  }
  % Inner cycle edges (T_2)
  \foreach \i in {0,1,2} {
    \pgfmathtruncatemacro{\j}{mod(\i+1,3)}
    \draw[orange!85!black, very thick] (vi\i) -- (vi\j);
  }
  % OUT pendants from outer hexagon (depth 0, cut) at v1, v3, v5
  \foreach \i in {1,3,5} {
    \pgfmathsetmacro{\ang}{60*\i + 90}
    \coordinate (p\i) at (\ang:\Rout+0.65);
    \draw[red, thick, dashed] (vo\i) -- (p\i);
    \node[circle, draw=red, fill=white, inner sep=1pt] at (p\i) {};
  }
  % Shared spokes between outer hexagon and inner triangle:
  % depth-2 edges = T_∂'s IN pendants AND T_2's OUT spokes
  \draw[green!55!black, thick, dashed] (vo0) -- (vi0);
  \draw[green!55!black, thick, dashed] (vo2) -- (vi1);
  \draw[green!55!black, thick, dashed] (vo4) -- (vi2);
  % T_2's IN pendants at inner vertices (depth 3)
  \foreach \i in {0,1,2} {
    \pgfmathsetmacro{\ang}{120*\i + 90 + 60}
    \coordinate (qi\i) at ([shift={(\ang:0.45)}]vi\i);
    \draw[purple, thick, dashed] (vi\i) -- (qi\i);
    \node[circle, fill=purple, inner sep=1pt] at (qi\i) {};
  }
  % Annotations
  \node[blue] at (-2.65, 1.75) {\small $T_\partial$ cycle};
  \node[blue] at (-2.65, 1.45) {\small (depth 1)};
  \node[orange!85!black] at (-1.85, -0.05) {\small $T_2^{(f')}$};
  \node[orange!85!black] at (-1.85, -0.35) {\small (depth 2)};
  \node[red] at (2.75, 1.65) {\small cut};
  \node[red] at (2.75, 1.35) {\small (depth 0)};
  \node[green!55!black] at (2.75, -1.35) {\small shared:};
  \node[green!55!black] at (2.75, -1.65) {\small IN of $T_\partial$};
  \node[green!55!black] at (2.75, -1.95) {\small $=$ OUT of $T_2$};
  \node[purple] at (0, -0.85) {\small depth 3};
\end{tikzpicture}
\end{center}

The green dashed edges are the \emph{shared} depth-$2$ edges:
they are IN pendants of $T_\partial$ \emph{and} OUT spokes of
$T_2^{(f')}$.  In any global $3$-edge coloring of $G'_i$, the
color assigned to each green edge is the same when viewed from
either tire.  The chain DP exploits exactly this shared-edge
identity.

\section*{The extended forest}

The high-side cut tire forest of $G'_i$ (proven in
\texttt{cut\_tire\_tree\_structure.tex}) has roots
$T_1^{(f_\text{high})}$ for the high-side faces of $H_1$.

\begin{defn}[Extended cut tire structure]
The \emph{extended cut tire structure} on side $i$ is the
high-side forest with $T_\partial^{(i)}$ adjoined as a
\emph{boundary node}.  $T_\partial$ is not a child or parent of any
high-side cut tire in the geometric containment sense, but it
\emph{shares edges} with adjacent high-side tires:
\begin{itemize}
\item $T_\partial$ shares depth-$1$ edges with each high-side
      depth-$1$ tire $T_1^{(f_\text{high})}$ whose face $f_\text{high}$
      is adjacent to $f_\partial$ (= shares a boundary edge of $H_1$).
\item $T_\partial$'s IN pendants are cycle edges of depth-$2$
      cut tires $T_2^{(f')}$ in adjacent high-side $H_1$ faces.
\end{itemize}
\end{defn}

\paragraph{Role in the chain DP.}  In the joint-projection chain DP,
the per-tire state at $T_\partial$ is a set of valid edge
$3$-colorings of $T_\partial$'s structure (cycle + OUT + IN
pendants).  Composition with adjacent tires is via shared edges
(same $G'_i$ edge tuple appearing in both), exactly as for the
high-side forest.  The chain DP then has $T_\partial$ as its
\emph{boundary interface}: the OUT pendants project to the cut, and
the IN pendants + cycle edges propagate constraints to/from the
high-side forest.

\section*{Chain DP with $T_\partial$, sketched}

\begin{enumerate}
\item Process the high-side forest bottom-up as before, producing
      per-tire valid coloring sets $A(T)$.
\item Compute the valid coloring set $A(T_\partial^{(i)})$ via
      enumeration of proper $3$-edge-colorings on $T_\partial$'s
      structure.
\item Restrict $A(T_\partial)$ by edge-sharing with adjacent
      high-side tires:
      \begin{itemize}
      \item For each $T_1^{(f_\text{high})}$ sharing depth-$1$ edges
            with $T_\partial$: keep $T_\partial$ colorings consistent
            with some $A(T_1^{(f_\text{high})})$ coloring on shared
            edges.
      \item For each $T_2^{(f')}$ sharing a depth-$2$ edge with
            $T_\partial$'s IN pendants: keep $T_\partial$ colorings
            consistent with some $A(T_2^{(f')})$ coloring on the
            shared edge.
      \end{itemize}
\item Project $A(T_\partial^{(i)})$ to OUT pendants $=$
      $\mathcal{R}_i$.
\end{enumerate}

\section*{Where things stand}

\paragraph{What this closes.}  The coverage gap (no high-side cut
tires on thin sides) is resolved: $T_\partial$ always exists and
provides the interface to the cut.

\paragraph{What it leaves open.}  $T_\partial$'s ``cycle'' is the
boundary walk of $f_\partial$, which is a closed walk in $H_1$ ---
\emph{not} necessarily a simple cycle when $H_1$ is a tree (the walk
traverses each edge twice).  The per-tire half (Prop 1.13) does not
directly apply to such walks.  This is a special case of the
``branched cut tires'' open problem in
\texttt{chain\_half\_analysis.tex}.

\paragraph{Why the chain DP can still work.}  Even without the
per-tire half guaranteeing $|\pi(T_\partial)| \ge 6$, we can
\emph{compute} the valid coloring set for $T_\partial$ directly
(brute-force or constraint-propagated enumeration).  If this set
is non-empty after edge-sharing restrictions, the chain DP yields
a non-empty $\mathcal{R}_i$.

\paragraph{Logical status of the extended framework.}
\begin{itemize}
\item Edge-sharing chain DP $S_3$-equivariance: still holds
      (uniform $S_3$ action commutes with edge constraints).
\item Tree structure: the high-side forest still forms a forest;
      $T_\partial$ adjoined is no longer a tree but a connected
      structure (forest + boundary node).
\item Per-tire half for $T_\partial$: open, special case of
      branched tires.
\item Non-emptiness of $\mathcal{R}_i$ via the DP: open; this is
      the \emph{primary} chain-half claim, now testable with
      $T_\partial$ included.
\end{itemize}

\section*{Empirical next step}

Re-run \texttt{chain\_dp\_joint.py} with $T_\partial$ added.
Compare with ground truth (brute-force $G'_i$ $3$-edge colorings).

For the dodecahedron cut $\#0$ side $0$:
\begin{itemize}
\item Ground truth: $|\mathcal{R}_\text{ground}| = 36$.
\item Old high-side-only DP: $|\mathcal{R}_0| = 0$ (no high-side
      tires).
\item New $T_\partial$-extended DP: should match ground truth (or
      reveal another gap to investigate).
\end{itemize}

\end{document}
