\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb} \usepackage[margin=1in]{geometry} \usepackage{booktabs,longtable,array,calc} \usepackage{graphicx,xcolor,fancyvrb} \usepackage{float} \usepackage{xurl} \usepackage[unicode,hidelinks]{hyperref} \hypersetup{pdftitle={Gallai's conjecture with two exceptional even vertices},pdfauthor={Idris Ali Shaik},pdfsubject={Graph theory; path decomposition},pdfkeywords={Gallai conjecture, path decomposition, even-degree vertices, Lean}} \setcounter{secnumdepth}{0} \providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}} \providecommand{\passthrough}[1]{#1} \setlength{\emergencystretch}{2em} \setlength{\parskip}{0.25em} \title{Gallai's conjecture with two exceptional even vertices} \author{Idris Ali Shaik\\ \small Independent researcher (unaffiliated)\\ \small \href{mailto:shaikidris@apache.org}{shaikidris@apache.org}\\ \small ORCID: \href{https://orcid.org/0009-0009-9699-9712}{0009-0009-9699-9712}} \date{5 October 2026} \newcounter{none} \begin{document} \maketitle \begin{abstract} Gallai conjectured that every connected finite simple graph on \(n\) vertices admits an edge partition into at most \(\lceil n/2\rceil\) simple paths. Botler and Sambinelli proved this when every even-degree vertex has at most three even neighbours. Fan, Hou and Zhou exempted one designated even vertex of positive degree and ensured that at least two paths ended there. Xie obtained the same endpoint conclusion for either of two adjacent designated even vertices, in separate partitions, when every other even vertex has at most three even neighbours. We prove that the same endpoint conclusion holds without requiring the two designated even vertices to be adjacent. Let \(F\) be the subgraph induced by the even-degree vertices of a connected finite simple graph \(G\) on \(n\) vertices, and let \(h,x\) be distinct vertices of \(F\). Suppose every other vertex of \(F\) has degree at most three in \(F\). Then for each of \(h\) and \(x\) there is an edge partition into at most \(\lceil n/2\rceil\) simple paths, at least two of which end at that vertex. Consequently, Gallai's bound holds whenever at most two vertices of \(F\) have degree greater than three. The two choices may use different partitions. We also obtain one partition with at least two paths ending at each member of the pair, using at most \(\lfloor n/2\rfloor+1\) paths. At odd order this is Gallai's bound. At even order the extra path can be necessary: \(K_4\) minus an edge requires three paths when both degree-two vertices are prescribed. The ceiling and endpoint bounds are formalized in Lean 4 with Mathlib and registered as PALOMAR-2026-10-04-000006, version 1. \end{abstract} \section{1. Introduction and statements}\label{introduction-and-statements} A path decomposition partitions the edges of a graph into nonempty simple paths. Paths in the decomposition may share vertices, but each edge belongs to exactly one path. Write \(p(G)\) for the minimum number of paths in such a partition. Gallai's conjecture asserts that \[ p(G)\le \left\lceil\frac{|V(G)|}{2}\right\rceil \] for every connected finite simple graph \(G\). Several sufficient conditions depend on the subgraph induced by its even-degree vertices. We prove the bound when at most two vertices have more than three neighbours in this subgraph. When there are two such vertices, we can also require at least two paths to end at either one of them. A vertex is \emph{even} or \emph{odd} according to the parity of its degree. Phrases such as ``odd in \(J\)'' specify the graph when it differs from \(G\). Let \(EV(G)\) denote the subgraph induced by the vertices of even degree in \(G\), and put \(F=EV(G)\). The degree \(d_F(v)\) of a vertex in this subgraph counts its neighbours that have even degree in \(G\). Call \(v\) an exception when \(d_F(v)>3\). Botler and Sambinelli proved Gallai's bound when there are no exceptions; their theorem also gives the stronger floor bound except for a specified family of odd-order graphs {[}BS, Theorem 13 and Corollary 14{]}. Fan, Hou and Zhou allow a designated even vertex of positive degree to have arbitrary degree in \(F\) and ensure that at least two paths end there {[}FHZ, Theorem 5{]}. Xie allows two adjacent designated even vertices and gives a separate decomposition with this endpoint property for either one {[}X, Theorem 1.4{]}. For a decomposition \(\mathcal D\), let \(\mathcal D(v)\) count its endpoint occurrences at \(v\), and put \(k(G)=\lceil |V(G)|/2\rceil\). Since the paths are nonempty and simple, \(\mathcal D(v)\ge2\) means that at least two different paths end at \(v\). A floor decomposition uses at most \(\lfloor |V(G)|/2\rfloor\) paths, and a ceiling decomposition uses at most \(k(G)\). \textbf{Theorem 1.1 (prescribed endpoint).} Let \(G\) be a connected finite simple graph, and let \(h,x\) be distinct even vertices with \(d_G(h)>0\). Suppose \[ d_F(v)\le3\qquad(v\in V(F)\setminus\{h,x\}). \] Then \(G\) has a path decomposition \(\mathcal D\) satisfying \[ |\mathcal D|\le k(G),\qquad \mathcal D(h)\ge2. \] Interchanging \(h\) and \(x\) gives the same conclusion with \(x\) prescribed; the two choices may use different decompositions. No upper bound is imposed on \(d_F(h)\), \(d_F(x)\), the degrees in \(G\), or the number of odd vertices. \textbf{Corollary 1.2.} Let \(G\) be a connected finite simple graph. If at most two vertices of \(EV(G)\) have degree greater than three in that subgraph, then \(p(G)\le k(G)\). \emph{Proof.} If \(G\) has no exception, the bound for graphs with subcubic \(EV(G)\) applies {[}BS, Theorem 13 and Corollary 14{]} (the one-vertex graph has the empty decomposition). If \(G\) has exactly one exception, that vertex has positive degree, and the one-exception theorem gives the ceiling bound {[}FHZ, Theorem 5{]}. If \(G\) has two exceptions, both have positive degree; Theorem 1.1, with either one prescribed, gives the ceiling bound. \(\square\) In \(K_4\) minus an edge, the two nonadjacent vertices have degree two and the other two have degree three. Two paths ending at each even vertex contribute four endpoint occurrences, and each odd vertex needs at least one more. The total is at least six, whereas two paths have only four. For odd-order graphs one decomposition has at least two paths ending at each designated vertex. More generally, Proposition 3.1 gives this conclusion within \(\lfloor |V(G)|/2\rfloor+1\) paths at every order. Removing adjacency strictly enlarges the class in Xie's statement. For example, \(K_{2,4}\) has precisely two vertices of degree four in \(F\), which are nonadjacent. Its path bound is already known from planar results {[}BBB{]}; here it illustrates the difference between the two hypotheses. \textbf{Proof sketch.} Adding or deleting the edge \(hx\) makes both designated vertices odd and leaves an even subgraph of maximum degree at most three. The published bounds of Section 2 then yield a decomposition from which we recover two endpoints at each designated vertex, using at most one path above the floor bound (Section 3). At odd order this is Gallai's bound. At even order \(|V(G)|=2m\), first suppose \(h\) is isolated in \(F\). The cut reductions and edge deletions in Sections 4--5 reduce a minimum counterexample to one whose even subgraph consists of triangles sharing \(x\), together with separate triangles and isolates. A shortest path from the triangles at \(x\) to another even vertex determines the restoration cases. The contact deletions in Sections 6--7 make \(x\) odd. Published component bounds then give at most \(m\) paths on \(2m\) vertices. Lemma 6.1 handles a reserved edge whose final restoration transfers an endpoint; Section 7 restores all remaining edges and leaves at least two endpoints at \(h\), without adding a path. For \(d_F(h)>0\), Section 8 first reduces cuts at \(h\). If \(d_F(h)\) is odd, deleting all its edges to even neighbours makes \(h\) odd and leaves at most the exception \(x\). If \(d_F(h)\) is positive and even, keep one such edge \(hv\) and prescribe \(v\) in the smaller graph. In both cases, restoration of the missing odd star supplies the two endpoints at \(h\). Theorem 1.1, Corollary 1.2, Proposition 3.1 and Corollary 3.2 are formalized in Lean 4 with Mathlib. Section 10 identifies the corresponding declarations and their verification record. \section{2. Published inputs and endpoint bookkeeping}\label{published-inputs-and-endpoint-bookkeeping} Deleting an edge set from \(G\) retains the vertex set, including isolates. The support of the deleted edge set consists of its incident vertices. For a graph \(G\) and a path decomposition \(\mathcal D\), endpoint parity gives \[ \mathcal D(v)\equiv d_G(v)\pmod2, \] so at least one path ends at every odd vertex. We write \(\mathcal D(w)=0\) when no path ends at \(w\); such conditions always refer to the graph currently being decomposed. Restoring a missing edge \(uv\) \emph{towards} \(u\) means replacing the current decomposition by one with the same number of paths, one more endpoint at \(u\), and one fewer at \(v\). The paths may be rearranged during restoration. The endpoint counts at all other vertices stay unchanged. For a missing star at \(u\), inward restoration makes this transfer along each restored edge; outward restoration reverses the transfers. We use the following published results. \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \item \textbf{Subcubic even subgraph.} If the even subgraph of a connected graph has maximum degree at most three, it has the floor bound unless it is a SET graph {[}BS, Theorem 13{]}. A SET (\textbf{single even triangle}) graph has exactly three even vertices forming a triangle, and each odd vertex has at least two neighbours in that triangle. SET graphs have odd order. For any prescribed vertex \(c\) of a SET graph, a ceiling decomposition can be chosen with \(\mathcal D(c)\ge2\) {[}BS, Lemma 10 and Corollary 14{]}. \item \textbf{One designated even vertex.} If a connected graph has an even vertex \(c\) of positive degree and every other even vertex has at most three even neighbours, there is a ceiling decomposition with \(\mathcal D(c)\ge2\) {[}FHZ, Theorem 5{]}. If a connected graph has no even vertex of positive degree, Lovász's floor bound for graphs with at most one even vertex applies {[}L; BS, Theorem 2(a){]}. \item \textbf{Two adjacent designated vertices.} In a connected graph with two adjacent designated even vertices, if every other even vertex has at most three even neighbours, there is a ceiling decomposition with at least two paths ending at either designated vertex separately {[}X, Theorem 1.4{]}. \item \textbf{Restoring one edge.} A missing edge \(uv\) can be restored towards \(u\), without increasing path count, if \(\mathcal D(v)\) exceeds the number of neighbours \(w\) of \(u\) with \(\mathcal D(w)=0\). Endpoint counts change by \(+1\) at \(u\), \(-1\) at \(v\), and zero elsewhere {[}Fan, Lemma 3.4; BS, Lemma 6{]}. \item \textbf{Half-star lemma.} Let \(\mathcal D\) decompose \(H\), and let \(S\) be a nonempty missing star at \(u\). If \(\mathcal D(w)>0\) for every \(w\in N_{H+S}(u)\), then for any prescribed edge of \(S\) there is a subset \(S'\subseteq S\) containing that edge, of size at least \(\lceil |S|/2\rceil\), which can be restored towards \(u\) {[}Fan, Lemma 3.6; BS, Lemma 7{]}. The resulting decomposition has the same path count, gains \(|S'|\) endpoints at \(u\), and loses one at each leaf of \(S'\); all other endpoint counts are unchanged. The hypothesis includes both missing-star leaves and retained neighbours. \end{enumerate} If a decomposition from inputs 1--3 contains trivial paths (paths with no edges), each contributes two endpoint occurrences at its vertex. Discard all such paths. Suppose fewer than two endpoints remain at a designated vertex \(c\) that had at least two in the input decomposition. At least one trivial path at \(c\) was discarded, and a nonempty path contains \(c\) as an internal vertex. Indeed, if \(c\) has positive even degree, its remaining endpoint count is even and therefore zero. If \(c\) is an odd vertex of a SET graph, its degree is at least three and its remaining endpoint count is one. Split a path at \(c\). Discarding a trivial path at \(c\) saved one path, so the split retains the original size bound and leaves \(c\) with at least two endpoints. \textbf{Lemma 2.1 (star restoration).} Suppose a missing star has \(k\) edges and its centre starts with \(d\) endpoints. Restore a subset of size \(a\) towards the centre, leaving \(b=k-a\) pending edges. Its prospective final endpoint count is \[ \sigma=d+a-b=d+2a-k. \] Suppose every pending leaf has at most two neighbours \(w\) with \(\mathcal D(w)=0\). All pending edges can be restored outward if \(\sigma\ge2\). They can also be restored if \(\sigma\ge1\) and some pending leaf has at most one such neighbour, by leaving that leaf until last. Thus, when \(\sigma\ge1\), failure is possible only if \(\sigma=1\) and every pending leaf has two such neighbours. With no pending edge, restoration is already complete. \emph{Proof.} With \(r\) edges still pending, the centre has \(\sigma+r\) endpoints. This is at least three while \(r\ge2\), and at the last step it exceeds the number of neighbours \(w\) of the recipient with \(\mathcal D(w)=0\). Input 4 therefore restores the edge. Each outward addition gives its leaf an endpoint, while at least one endpoint remains at the centre. The number of such neighbours therefore cannot increase at any leaf. \(\square\) In the applications below, the half-star lemma supplies the inward subset. An odd missing star whose centre is odd before restoration has \(\sigma\ge2\). For a centre odd in \(G\) from which \(k\) edges were removed, parity instead gives \(d\ge\mathbf1[k\text{ even}]\), and a half-star gives \(\sigma\ge1\). Here \(\mathbf1[P]\) equals \(1\) if \(P\) holds and \(0\) otherwise. \textbf{Lemma 2.2 (component budgets).} If all components on a total of \(N\) vertices have their floor bounds, their union uses at most \(\lfloor N/2\rfloor\) paths. If one component instead receives its ceiling, the total is at most \(\lceil N/2\rceil\). Indeed, writing each component order as twice an integer plus its parity, the sum of all floors is \((N-o)/2\), where \(o\) is the number of odd components. The single ceiling can add one only when \(o\ge1\). \textbf{Lemma 2.3 (gluing).} Suppose two connected edge-disjoint graphs \(A,B\) meet only at \(c\), with \(d_A(c)>0\) and \(d_B(c)>0\). Joining one \(c\)-ending path from each side saves one path. If one side has at least two paths ending at \(c\) and the other has no endpoint there, split a path through \(c\) on the latter side and join its two arms to two \(c\)-ending paths on the first side. This also saves one path. Simplicity follows from the one-vertex intersection, and endpoint counts away from \(c\) are unchanged. \textbf{Lemma 2.4 (neighbours with \(\mathcal D(w)=0\) after a star deletion).} Let \(F=EV(G)\), and obtain a current graph \(J\) by deleting some edges joining a centre \(c\), even in \(G\), to leaves that are even in \(G\). If a deleted edge \(cw\) is still missing and \(d_F(w)\le3\), then for every decomposition \(\mathcal D\) of \(J\), \[ \{v\in N_J(w):\mathcal D(v)=0\} \subseteq N_F(w)\setminus\{c\}, \qquad |\{v\in N_J(w):\mathcal D(v)=0\}| \le d_F(w)-1\le2. \] \emph{Proof.} Every vertex odd in \(G\) remains odd in \(J\). A neighbour \(v\) with \(\mathcal D(v)=0\) must be even in \(J\), hence even in \(G\), and \(c\) is not a current neighbour of \(w\). The same argument applies after each partial restoration, regardless of the current parity of \(c\). \(\square\) \textbf{Lemma 2.5 (trimming a pendant edge).} Add a new leaf \(v'\) at a vertex \(v\) of \(G\), obtaining \(G^+=G+vv'\), and let \(\mathcal D^+\) decompose \(G^+\). If the path containing \(vv'\) has at least two edges, trimming \(vv'\) preserves the path count and adds one endpoint at \(v\). If it is a one-edge path, discarding it saves one path and removes one endpoint at \(v\). Endpoint counts at all other vertices of \(G\) are unchanged. In particular, when \(v\) has positive even degree in \(G\), one obtains a decomposition with at least two paths ending at \(v\) and no more paths than \(\mathcal D^+\). \emph{Proof.} The leaf \(v'\) is an end of the path containing \(vv'\), so trimming has the stated effects. If \(v\) has positive even degree in \(G\), its endpoint count in \(\mathcal D^+\) is odd. Trimming a path with at least two edges therefore leaves at least two endpoints at \(v\). After discarding a one-edge path, the remaining endpoint count at \(v\) is even. If it is zero, positive degree ensures that some path contains \(v\) as an internal vertex. Split it at \(v\). This adds one path, so the total path count is unchanged. \(\square\) \section{3. Simultaneous endpoints with one unit of slack}\label{simultaneous-endpoints-with-one-unit-of-slack} We first obtain a decomposition with at least two paths ending at each designated vertex, using at most one path above the floor bound. At odd order this is Gallai's bound, and Section 4 uses it for odd-order pieces. \textbf{Proposition 3.1.} Let \(G\) be a connected finite simple graph, and let \(h,x\) be distinct positive-degree even vertices. If \(d_F(v)\le3\) for every even vertex \(v\notin\{h,x\}\), then \(G\) has a path decomposition \(\mathcal D\) such that \[ |\mathcal D|\le\left\lfloor\frac{|V(G)|}{2}\right\rfloor+1, \qquad \mathcal D(h),\mathcal D(x)\ge2. \] \emph{Proof.} Write \(n=|V(G)|\). First suppose \(hx\notin E(G)\), and set \(J=G+hx\). This graph is connected and simple, with \(EV(J)=F-\{h,x\}\) subcubic. It cannot be SET. In a SET graph, the now-odd vertices \(h,x\) would each have at least two neighbours in the even triangle, giving at least four edges from \(h,x\) to that triangle. Each triangle vertex has two even neighbours within the triangle and degree at most three in \(F\), so at most three such edges can enter the triangle. Take a floor decomposition of \(J\). Delete \(hx\) from its unique path, and let \(t\in\{0,1,2\}\) be the number of empty pieces. After discarding them, the path count changes by \(1-t\). At a nonempty piece, the endpoint \(h\) or \(x\) gains one endpoint over its odd endpoint count in \(J\), and hence has at least two. Only an empty piece can leave one of these vertices with zero endpoints. Split a path through each such vertex if needed; positive degree in \(G\) ensures one exists. At most \(t\) splits suffice, and these splits do not decrease the endpoint count at the other designated vertex. The total increase is at most one. Next suppose \(hx\in E(G)\) is not a bridge. The graph \(J=G-hx\) is connected, has the same even subgraph \(F-\{h,x\}\), and is non-SET by the same incidence count. Add \(hx\) as a one-edge path to a floor decomposition of \(J\). Both \(h\) and \(x\) were odd in \(J\), so each had at least one endpoint and now has at least two. The path count increases by one. Finally suppose \(hx\) is a bridge. Let \(A,B\) be the two components of \(G-hx\), with \(h\in A\) and \(x\in B\). Both designated vertices are odd and have positive degree in their respective components. Every other vertex keeps its parity in \(G\), so both even subgraphs are subcubic. If neither component is SET, combine floor decompositions and the one-edge path \(hx\). Each designated vertex had an endpoint by odd degree, and \(hx\) gives it another. This gives \(\mathcal D(h),\mathcal D(x)\ge2\) using at most \[ \left\lfloor\frac{|A|}{2}\right\rfloor+ \left\lfloor\frac{|B|}{2}\right\rfloor+1 \le \left\lfloor\frac n2\right\rfloor+1 \] paths, where \(|A|,|B|\) denote the component orders. Otherwise interchange the sides if necessary so that \(A\) is SET. Input 1 of Section 2 supplies a ceiling decomposition of \(A\) with at least two endpoints at \(h\). Since \(h\) is odd in \(A\), its endpoint count is in fact at least three. Give \(B\) a ceiling decomposition. Extend one \(h\)-ending path of \(A\) by \(hx\); this is simple because \(x\notin V(A)\). The endpoint count at \(h\) drops by one and remains at least two, while the odd endpoint count at \(x\) increases by one and becomes at least two. No path is added. Since \(|A|\) is odd, \[ \left\lceil\frac{|A|}{2}\right\rceil+ \left\lceil\frac{|B|}{2}\right\rceil =\left\lfloor\frac n2\right\rfloor+1. \] This also covers the case when both components are SET. \(\square\) \textbf{Corollary 3.2 (odd order).} Under the hypotheses of Proposition 3.1, if \(|V(G)|\) is odd, the ceiling bound holds with at least two paths ending at each designated vertex. \emph{Proof.} The bound in Proposition 3.1 equals \(\lceil |V(G)|/2\rceil\) at odd order. \(\square\) Both statements use only the published inputs of Section 2, so Corollary 3.2 can be applied inside the minimum-counterexample arguments that follow. At even order the extra path is necessary in general. In \(K_4-hx\), the vertices \(h,x\) have degree two and the other vertices \(p,q\) have degree three. Two paths ending at each of \(h,x\) contribute four endpoint occurrences. Each of the odd vertices \(p,q\) needs at least one more, so there are at least six endpoint occurrences and hence at least three paths. The paths \((h,p,q,x)\), \((h,q)\), and \((p,x)\) achieve the bound. \begin{figure}[H] \centering \includegraphics[width=.80\linewidth,keepaspectratio]{figures/k4-minus-edge.png} \caption{The three paths partition \(K_4-hx\). The vertices \(h,x\) have degree two, and \(p,q\) have degree three. Solid, dash--dot and dotted lines distinguish the paths shown in the legend.} \label{fig:k4-minus-edge} \end{figure} For adjacent \(h,x\), Theorem 1.1 is {[}X, Theorem 1.4{]}. Together with Corollary 3.2, this shows that a counterexample to Theorem 1.1 has even order and nonadjacent designated vertices. \section{4. A prescribed vertex with no even neighbour}\label{a-prescribed-vertex-with-no-even-neighbour} Restoring a deleted edge can use up an endpoint at one of its ends. We first treat the case \(d_F(h)=0\), that is, \(h\) is isolated in \(F\). Then every neighbour of \(h\) is odd, and the edges we delete and restore inside \(F\) avoid \(h\). Throughout Sections 4--7, \(h\) is isolated in \(F\) and \(d_G(h)>0\). \textbf{Lemma 4.1.} Theorem 1.1 holds when \(d_F(h)=0\). \emph{Proof (Sections 4--7).} Suppose Lemma 4.1 fails. Among triples \((G,h,x)\) satisfying its hypotheses, choose a counterexample minimizing \((|V(G)|,|E(G)|)\) lexicographically. If \(x\) were not an actual exception, the one-exception input {[}FHZ{]} would give \(\mathcal D(h)\ge2\). Thus \(x\) is an exception and has positive degree. Corollary 3.2 makes the order even, say \(2m\). \textbf{Cuts.} The vertex \(x\) is not a cut vertex. Suppose it is. Form two nontrivial sides \(A\) and \(B\) meeting only at \(x\), with \(h\in A\): place the component of \(G-x\) containing \(h\) in \(A\), and every other component in \(B\). The local degrees \(d_A(x)\) and \(d_B(x)\) sum to the even number \(d_G(x)\), so they are both even or both odd. Every vertex other than \(x\) keeps its degree, so only \(x\) can change parity, and \(x\) is even in a side only when its local degree there is even. Hence every even vertex other than \(x\) still has at most three even neighbours in each side. Since \(h\) is isolated in \(F\), it is not adjacent to the even vertex \(x\); it keeps positive degree and stays isolated in the even subgraph of \(A\). The orders satisfy \(|A|+|B|=2m+1\), so the two ceiling bounds sum to \(m+1\). If both local degrees are odd, then \(x\) is odd in each side. The side \(A\) has an even subgraph of maximum degree at most three, and {[}FHZ{]} gives a ceiling decomposition with \(\mathcal D(h)\ge2\). The even subgraph of \(B\) has maximum degree at most three, and the ceiling bound in input 1 of Section 2 applies. Each side has an endpoint at \(x\). Lemma 2.3 joins one such path and saves one path. The resulting decomposition of \(G\) has at most \(m\) paths and \(\mathcal D(h)\ge2\). If both local degrees are even, then each is at least two, so \(x\) is even and has positive degree in each side. By minimality, Lemma 4.1 applies to \(A\), which has fewer vertices than \(G\), and gives \(\mathcal D(h)\ge2\). On \(B\), the vertex \(x\) is the only possible exception, so {[}FHZ{]} gives at least two paths ending at \(x\). The endpoint count of \(x\) in \(A\) is even. If it is nonzero, Lemma 2.3 joins one \(x\)-ending path from each side. If it is zero, the same lemma splits a path through \(x\) and joins both arms to the two \(x\)-ending paths in \(B\). Either operation saves one path and does not change the endpoints at \(h\). The total is again at most \(m\). An even vertex \(c\notin\{h,x\}\) cannot separate \(h\) from \(x\). Suppose it does. Let \(A\) be the subgraph induced by \(c\) and the component of \(G-c\) containing \(h\), and let \(B\) be induced by \(c\) and all remaining components, including the one containing \(x\). Both sides are connected and nontrivial and meet only at \(c\). Their local degrees \(d_A(c)\) and \(d_B(c)\) sum to the even number \(d_G(c)\), so they have the same parity. Vertices other than \(c\) keep their degrees and parities, and \(c\) is even in a side only when its local degree there is even. Only \(x\) is exceptional in \(G\), so \(d_F(c)\le3\), and \(c\) has at most three even neighbours in either side. Every other even vertex except \(x\) likewise has at most three even neighbours in each side. Since \(h\) is isolated in \(F\), it is not adjacent to \(c\); it keeps positive degree and stays isolated in the even subgraph of \(A\). The side orders again sum to \(2m+1\). If both local degrees are odd, then \(c\) is odd in each side, so each decomposition has an endpoint at \(c\). The side \(A\) does not contain \(x\), and {[}FHZ{]} gives \(\mathcal D(h)\ge2\). The side \(B\) has \(x\) as its only possible exception, and {[}FHZ{]} gives its ceiling bound. Lemma 2.3 saves one path, leaving at most \(m\) paths. If both local degrees are even, then \(c\) is even and has positive degree in each side, and exactly one side has odd order. When \(B\) is the odd side, Corollary 3.2 applied to \(c\) and \(x\) gives two paths ending at each within the ceiling of \(B\), while \(EV(A)\) has maximum degree at most three and {[}FHZ{]} gives \(\mathcal D(h)\ge2\). When \(A\) is the odd side, Corollary 3.2 gives two paths ending at each of \(h,c\) in \(A\), while \(B\) has \(x\) as its only possible exception and {[}FHZ{]} gives its ceiling bound. In each subcase the odd side has two endpoints at \(c\). On the even side the endpoint count at \(c\) is even. Lemma 2.3 joins one \(c\)-ending path from each side, or, when no path ends at \(c\) on the even side, splits a path through \(c\) and joins both arms. The saved path leaves at most \(m\) paths and \(\mathcal D(h)\ge2\). \textbf{Hanging SETs.} Components away from \(h\) will need their floor bounds, which a SET component may fail to have. Suppose an induced SET subgraph \(K\), avoiding \(h,x\), has the single boundary edge \(aq\), where \(q\in K\) is even in \(G\). Keep \(q\) and \(aq\), deleting the other vertices of \(K\). Since \(aq\) is the only edge leaving \(K\) and is kept, every vertex outside \(K\) keeps its degree and parity. The vertex \(q\) becomes an odd leaf; \(h\) keeps positive degree and stays isolated in the even subgraph. Indeed \(a=h\) is impossible because \(q\) was even. The reduced graph has fewer vertices, so minimality gives Lemma 4.1 there. Take a SET ceiling decomposition of \(K\). The vertex \(q\) is odd within \(K\); join paths ending there. The total is \[ \frac{2m-|K|+1}{2}+\frac{|K|+1}{2}-1=m. \] This excludes such hanging SET subgraphs. \textbf{Parity at \(x\).} If \(d_F(x)\) is odd, delete its entire even-neighbour star, obtaining \(J\). Since \(d_G(x)\) is even and \(d_F(x)\) is odd, \(x\) has a neighbour that is odd in \(G\); as \(x\) is not a cut vertex, \(J\) is connected. Its even subgraph has maximum degree at most three, and \(h\) keeps positive degree and stays isolated in it. Apply {[}FHZ{]} at \(h\). The missing star has odd size and its centre is odd. Every neighbour of \(x\) in the graph with the star restored is odd in \(J\), so at least one path ends at each, as required by the half-star input. No leaf is \(h\), since \(d_F(h)=0\); each leaf therefore has degree at most three in \(F\). By Lemma 2.4, every pending leaf has at most two neighbours \(w\) with \(\mathcal D(w)=0\) throughout restoration. Lemma 2.1 restores the star while keeping \(\mathcal D(h)\ge2\). Hence \(d_F(x)\) is even and at least four. \section{\texorpdfstring{5. Structure when \(h\) is isolated in \(F\)}{5. Structure when h is isolated in F}}\label{structure-when-h-is-isolated-in-f} Write \(W_r(x)\) for \(r\) triangles sharing their centre \(x\) and otherwise vertex-disjoint. This graph is a \emph{windmill}. Each triangle is a \emph{petal}, and its two vertices other than \(x\) are its private vertices. The edges joining them to \(x\) are the petal's \emph{spokes}; the edge joining the private vertices is its \emph{mate edge}. \textbf{The component of \(x\).} Suppose a vertex \(a\) with \(d_F(a)=3\) lies in this component. Choose a shortest path in \(F\) from \(x\) to such a vertex. Write it as \(v_0v_1\ldots v_t\), with \(v_0=x\) and \(v_t=a\). Its internal vertices have degree two in \(F\); let \(q,r\) be the other even neighbours of \(a\). Delete the path and \(aq,ar\), and add a new pendant edge \(hh'\). The added leaf makes the total order \(2m+1\), so floor decompositions of all components use at most \(m\) paths; Lemma 2.5 recovers two endpoints at \(h\) when the pendant is trimmed. The vertices \(x,a,q,r,h,h'\) become odd; internal path vertices become isolated in the even subgraph. Call the resulting graph \(J\). Its even subgraph has maximum degree at most three. A SET component can contain none of those even isolates, nor \(a\), nor the component containing \(hh'\). Its even triangle consists of vertices of \(F\) with degree at most three, so at most three edges of \(F\) leave that triangle. It can therefore contain at most one of \(x,q,r\), each of which would require two such incidences. Connectedness of \(G\) forces it to meet the deleted-edge support, so it contains exactly one of these three vertices and no other deleted-edge endpoint. No deleted edge is internal to the component; it is therefore induced in \(G\), with a unique boundary edge. If it contains \(x\), that edge is the first edge of the chosen path, making \(x\) a cut vertex. Otherwise the boundary is \(aq\) or \(ar\), giving an excluded hanging SET whose boundary vertex was even in \(G\). Every component thus has a floor decomposition. Their total order is \(2m+1\), so they use at most \(m\) paths. For \(1\le i0. \tag{K} \] \begin{figure}[H] \centering \includegraphics[width=.95\linewidth,keepaspectratio]{figures/even-subgraph-structure.png} \caption{One instance of (K), with three petals at \(x\), one ordinary triangle and the isolate \(h\). The private pairs are \(p_i,q_i\). This drawing shows \(F\); the odd neighbours of \(h\) in \(G\) lie outside it.} \label{fig:even-subgraph-structure} \end{figure} \section{6. Restoring contacts with a reserved edge}\label{restoring-contacts-with-a-reserved-edge} After Section 5, the only exception is the centre \(x\) of the windmill. Delete all but at most one edge from an odd vertex \(u\) to the windmill. Depending on the contacts, also delete at most one spoke and one mate edge, so that exactly one deleted edge meets \(x\). Thus \(x\) becomes odd. One further edge \(uv\), with \(v\) outside the windmill, is deleted as well and restored last: it carries an endpoint from \(u\) to \(v\). In Section 7 this endpoint either gives \(h\) its second endpoint or starts the restoration at \(v\). Let a vertex \(u\), odd in \(G\), have a nonempty set of even neighbours in \(W_r(x)\). Define: \begin{itemize} \tightlist \item \(\eta=\mathbf1[ux\in E(G)]\); \item \(n_1\) counts \emph{single petals}, in which \(u\) meets exactly one private vertex; \item \(n_2\) counts \emph{double petals}, in which \(u\) meets both private vertices. \end{itemize} In a single petal \((p,q)\), \(p\) is the contact. The following preparations specify a set \(C\) of deleted \(u\)-contact edges, including \(ux\) when \(\eta=1\). Rules E1--E5 cover every nonempty contact pattern. An asterisk subscript, as in \(q_*\), marks a private vertex of a petal chosen for that rule; \(p'\) is the private vertex whose contact edge \(up'\) is kept, and \(q'\) is its mate. {\def\LTcaptype{none} % do not increment counter \begin{longtable}[]{@{} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}}@{}} \toprule\noalign{} \begin{minipage}[b]{\linewidth}\raggedright Rule \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright Contact pattern \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright Deleted contact edges \(C\) \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright Other deletions \end{minipage} \\ \midrule\noalign{} \endhead \bottomrule\noalign{} \endlastfoot E1 & \(\eta=0,\ n_1\) odd & All & \(xq_*\), in a single petal \\ E2 & \(\eta=0,\ n_1\) even, \(n_2\ge1\) & All except \(uq_*\) & \(xq_*\), in a double petal \\ E3 & \(\eta=1,\ n_1\) even & All, including \(ux\) & None \\ E4 & \(\eta=1,\ n_1\) odd & All except \(up'\) & \(p'q'\), in a single petal \\ E5 & \(\eta=0,\ n_1\ge2\) even, \(n_2=0\) & All except \(up'\) & \(p'q'\) and \(xq_*\), in different single petals \\ \end{longtable} } The respective values of \(|C|\) are \(n_1+2n_2,n_1+2n_2-1,1+n_1+2n_2,n_1+2n_2,n_1-1\). They are odd. Exactly one deleted edge is incident with \(x\). Every touched private vertex is odd after these deletions. For \(\eta=1\), the parity of \(n_1\) selects E3 or E4. For \(\eta=0\), odd \(n_1\) selects E1; even \(n_1\) selects E2 when \(n_2\ge1\) and E5 otherwise. In the last case, nonempty contact gives \(n_1\ge2\). \begin{figure}[H] \centering \includegraphics[width=.95\linewidth,keepaspectratio]{figures/e1-e5-preparations.png} \caption{Representative instances of E1--E5 in \(G\). Dashed edges are deleted; solid edges are kept. Only selected petals and contact edges are shown. Other petals and the reserved edge \(uv\) are omitted.} \label{fig:e1-e5-preparations} \end{figure} \textbf{Lemma 6.1 (reserved-edge restoration).} In addition delete \(uv\), with \(v\) outside the windmill. Suppose other preparations (as in Section 7) avoid this windmill and \(u\). Let \(\mathcal D_0\) decompose the graph after all deletions. Assume the following conditions hold during restoration: \begin{itemize} \tightlist \item \textbf{(i)} \(\mathcal D(w)\ge1\) for each retained neighbour \(w\) of \(u\) outside \(W_r(x)\cup\{v\}\); \item \textbf{(ii)} \(\mathcal D(w)\ge1\) for each retained neighbour \(w\) of \(v\) until \(uv\) is restored; \item \textbf{(iii)} \(\mathcal D(w)\ge1\) for every vertex \(w\ne u\) that is odd in \(G\) and adjacent to a private vertex. \end{itemize} The edges deleted by E1--E5, together with \(uv\), can be restored without increasing the number of paths; the other deleted edges remain absent. The resulting decomposition \(\mathcal D_1\) satisfies \(\mathcal D_1(u)\ge1\) and \(\mathcal D_1(v)\ge\mathcal D_0(v)+1\). Endpoint counts change only at \(u,v,x\) and touched private vertices. \emph{Proof.} The vertex \(u\) lost an even number of edges and is odd. First restore \(p'q'\) towards \(p'\) in E4/E5, using \(\mathcal D(x),\mathcal D(u)\ge1\). Restore \(xq_*\) towards \(q_*\) in E1/E2/E5, using an endpoint at its mate and also at \(u\) in E2. Now \(\mathcal D(w)\ge1\) at each retained contact vertex \(w\). Apply the half-star lemma to \(C\): the current graph is the graph being decomposed, its hypothesis is checked in the current graph with \(C\) added, and \(uv\) is absent from both. Prescribe \(ux\) in E3/E4, since its untouched private neighbours may have endpoint count zero. The star and centre are odd. A pending private vertex has no current edge to \(u\), and every other neighbour odd in \(G\) has an endpoint by (iii). The only neighbours \(w\) with possibly \(\mathcal D(w)=0\) are its mate and \(x\). Hence restoration leaves \(\mathcal D(u)\ge2\). When \(|C|=1\), the half-star subset is the entire contact set, so the sole inward restoration already gives this bound. Restore \(uv\) towards \(v\); every retained neighbour \(w\) of \(v\) has \(\mathcal D(w)\ge1\), and \(\mathcal D(u)\ge1\) remains. \(\square\) \textbf{Example (one single-petal contact).} Let \(u\), odd in \(G\), have exactly two even neighbours: \(p\), in a petal \((p,q)\) of the windmill, and the prescribed vertex \(h\). Here \(\eta=0\) and \(n_1=1\), so rule E1 deletes \(up,xq\); take \(uh\) as the reserved edge. After these three deletions, \(u,x,p,q,h\) are odd, and every other vertex that was odd in \(G\) keeps its degree. \begin{figure}[H] \centering \includegraphics[width=.95\linewidth,keepaspectratio]{figures/e1-endpoint-transfers.png} \caption{The selected petal and the two contacts of \(u\). Dashed edges are deleted. The arrows show the endpoint transfers in steps 1--3 below; other incident edges are omitted.} \label{fig:e1-endpoint-transfers} \end{figure} Starting with any decomposition of this graph, restore the edges as follows: \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Restore \(xq\) towards \(q\). The retained neighbours of \(q\) are \(p\) and unchanged odd vertices, so input 4 applies using an endpoint at \(x\). \item Restore \(up\) towards \(u\). The retained neighbours of \(u\) are unchanged odd vertices, and \(p\) still has an endpoint. This gives \(\mathcal D(u)\ge2\). \item Restore \(uh\) towards \(h\). The retained neighbours of \(h\) are unchanged odd vertices, so input 4 applies. The endpoint count at \(h\) increases from an odd positive value, giving \(\mathcal D(h)\ge2\), while \(\mathcal D(u)\ge1\) remains. \end{enumerate} The three restorations use no additional path. \section{\texorpdfstring{7. Completing the proof when \(h\) is isolated in \(F\)}{7. Completing the proof when h is isolated in F}}\label{completing-the-proof-when-h-is-isolated-in-f} Connectivity gives a path from the windmill to another even vertex. Its length decides how Lemma 6.1 is combined with the restoration of edges to ordinary components. Choose a shortest path in \(G\) from \(W_r(x)\) to an even vertex outside it. Such a vertex exists because \(h\) is outside and has positive degree. The internal vertices are odd and the length is at least two. The three cases are length at least three, length two with an even contact only at \(h\) outside the windmill, and length two with other ordinary contacts. In each case let \(J\) be the graph after the deletions. It has \(2m\) vertices, \(x\) is odd in \(J\), and \(EV(J)\) has maximum degree at most three. If \(h\) remains even, {[}FHZ{]} gives the ceiling bound and two endpoints at \(h\) on its component. A component avoiding \(h\) receives a floor bound once it contains either an odd vertex with at most one even neighbour or an even vertex of degree at most one in \(EV(J)\): either vertex rules out an odd SET component. We call such a vertex a \emph{witness}. Lemma 2.2 then gives at most \(m\) paths in total. If \(h\) becomes odd with no even neighbour, its component also receives a floor bound. The preparations in each case supply these witnesses. \subsection{Two consecutive odd internal vertices}\label{two-consecutive-odd-internal-vertices} For length at least three, let \(u,v\) be the first two internal vertices. All even neighbours of \(u\) lie in the windmill, and \(v\) has no even neighbour there. At length at least four \(v\) has no even neighbour; at length three it can meet ordinary components. Keep \(vh\) if present. Prepare every other contacted ordinary component using the following table, where the stated vertices are the contacts of \(v\). The deletions in this table are called \emph{regular preparations}. {\def\LTcaptype{none} % do not increment counter \begin{longtable}[]{@{}lll@{}} \toprule\noalign{} Component & Contacts & Deleted edges \\ \midrule\noalign{} \endhead \bottomrule\noalign{} \endlastfoot I: Isolate \(A\) & \(A\) & \(vA\) \\ T1: Triangle \(ABC\) & \(A\) & \(vA,BC\) \\ T2: Triangle \(ABC\) & \(A,B\) & \(vA,BC\) \\ T3: Triangle \(ABC\) & \(A,B,C\) & \(vA,vB,vC\) \\ \end{longtable} } \begin{figure}[H] \centering \includegraphics[width=.95\linewidth,keepaspectratio]{figures/ordinary-contact-preparations.png} \caption{The regular preparations in the table. Dashed edges are deleted; solid edges are kept. The triangle edges lie in \(F\), and \(v\) is odd in \(G\). Other neighbours of \(v\) are omitted.} \label{fig:ordinary-contact-preparations} \end{figure} Delete \(uv\) and prepare \(u\)'s windmill contacts by E1--E5. Among vertices odd in \(G\), only \(v\) can become even; its only possible even neighbour is then \(h\). The vertex \(h\) remains even and has positive degree. Every other component meets the deleted-edge support, since \(G\) was connected. The vertices \(u,v\) have at most one even neighbour, and every other support vertex except \(x\) is odd with at most one even neighbour or even with degree at most one in \(EV(J)\). If the component contains \(x\), a retained spoke places a private vertex with one of these properties in that same component; at least one spoke remains because \(r\ge2\) and at most one was deleted. Thus each such component has a witness. Use {[}FHZ{]} with \(\mathcal D(h)\ge2\) on its component and floors elsewhere. The total is at most \(m\). The ordinary preparations avoid the windmill and \(u\). The conditions of Lemma 6.1 hold throughout restoration: \begin{itemize} \tightlist \item \textbf{(i)} The retained neighbours of \(u\) outside the windmill are unchanged odd vertices. \item \textbf{(ii)} The retained neighbours of \(v\) are \(h\), the odd vertex \(B\) in each regular T2 preparation, and unchanged odd vertices. \item \textbf{(iii)} The vertex \(v\) has no windmill neighbour, so every vertex other than \(u\) that is odd in \(G\) and adjacent to a private vertex stays odd. \end{itemize} Apply Lemma 6.1 to restore \(u\)'s side and \(uv\). If \(k\) ordinary \(v\)-edges were removed, then before \(uv\) is restored \(v\) has lost \(k+1\) edges, so its endpoint count before restoration is at least \(\mathbf1[k\text{ odd}]\). Lemma 6.1 adds one, giving \(\mathcal D(v)\ge1+\mathbf1[k\text{ odd}]\). Restore every prepared \(BC\) towards \(B\): its retained neighbours are all odd in T1; in T2, \(v\) also remains adjacent and \(\mathcal D(v)\ge1\). Thus input 4 of Section 2 applies. In particular, \(B\) now has at least two endpoints. All retained \(v\)-neighbours have \(\mathcal D(w)\ge1\), so apply the half-star lemma to the missing edges at \(v\). For odd \(k\), \(\sigma\ge3\). For even \(k\), \(\sigma\ge1\). In a failure, every pending leaf would have two neighbours \(w\) with \(\mathcal D(w)=0\). An isolate contact has none, and a one- or two-contact triangle's contact \(A\) has at most one, since \(B\) retains its endpoints. These contacts must therefore be selected. In a three-contact triangle, both mates \(w\) of a pending contact can have \(\mathcal D(w)=0\) only if both were selected. Thus each component contributes at least one to \(a-b\). For even \(k>0\) this contradicts \(\sigma=1\), which requires \(a-b=0\); for \(k=0\) there is nothing to restore. All moves keep \(\mathcal D(h)\ge2\). \subsection{A contact only with the prescribed isolate}\label{a-contact-only-with-the-prescribed-isolate} For a length-two path, let \(u\) be its middle vertex. Suppose its only even contact outside the windmill is \(h\). Use \(uh\) as the reserved edge. Now \(h\) is odd with no even neighbour. The other components have the same witnesses as above; thus all components get floors, using at most \(m\) paths. The conditions of Lemma 6.1 hold: \begin{itemize} \tightlist \item \textbf{(i)} The retained neighbours of \(u\) outside the windmill are unchanged odd vertices. \item \textbf{(ii)} The retained neighbours of \(h\) are unchanged odd vertices. \item \textbf{(iii)} Every vertex other than \(u\) that is odd in \(G\) and adjacent to a private vertex is unchanged and odd. \end{itemize} Lemma 6.1 restores \(uh\) towards \(h\), increasing the endpoint count there by one. Since \(h\) starts odd, its final endpoint count is at least two. \subsection{Other ordinary contacts}\label{other-ordinary-contacts} Suppose \(u\) meets \(N\ge1\) ordinary components other than \(\{h\}\). Keep \(uh\) if present. Denote their types by I, T1, T2, T3 according to the preceding table. For T2 we may instead delete \(uA,uB\), a \emph{special} preparation leaving \(C\) even with degree zero in \(EV(J)\). At most one T2 is special; let \(\epsilon\in\{0,1\}\) count it. If \(o\) ordinary \(u\)-edges are deleted, \(o\equiv N+\epsilon\pmod2\). Write \(k\) for the total deleted \(u\)-edges and \(d_0=\mathbf1[k\text{ even}]\). Since \(u\) was odd, \(d_0\) is the parity lower bound for its endpoint count before restoration. When a regular choice would make \(k\) odd and T2 is available, make one T2 special. Then \(\epsilon\le d_0\). Whenever regular T2 preparations remain, \(\mathcal D(u)\ge1\) before restoration, so their \(BC\) edges restore towards \(B\) before the star: the retained neighbours of \(B\) are odd vertices and \(u\). In T1, \(uB\) is absent, so the retained neighbours of \(B\) are all odd. Suppose a half-star fails with \(\sigma=1\) and all pending leaves having two neighbours \(w\) with \(\mathcal D(w)=0\). Each I, T1, regular T2 and T3 contributes at least one to \(a-b\). A special T2 contributes at least zero: if neither contact were selected, the two pending mates would retain their endpoints and neither could have two such neighbours. When a private vertex is contacted, choose a spoke petal \((p_*,q_*)\), double if possible, otherwise single with \(p_*\) contacted. A \emph{spare} petal means any other contacted petal. We use four schedules: a contact only at \(x\); private contacts covered by the five-row table below; the remaining private-contact cases with \(N\ge2\); and finally \(N=1\) of type T3. \paragraph{\texorpdfstring{Only \(x\) is contacted}{Only x is contacted}}\label{only-x-is-contacted} Delete \(ux\) and the ordinary preparations, so \(k=1+o\), and use the special-T2 rule. The vertex \(x\) is odd. A newly even \(u\) has at most the even neighbour \(h\), and each private vertex has only its mate as a possible even neighbour. Every component avoiding \(h\) meets deletion support; an ordinary support vertex or \(u\) supplies a witness, while a component containing \(x\) contains a private vertex along a retained spoke. The component bounds therefore give at most \(m\) paths and two endpoints at \(h\). Restore the regular \(BC\) edges, then prescribe \(ux\) in the half-star. Failure would imply \[ 1+N-\epsilon\le1-d_0, \] contrary to \(N\ge1\) and \(\epsilon\le d_0\). \paragraph{\texorpdfstring{Using the endpoint at \(x\) after the star}{Using the endpoint at x after the star}}\label{using-the-endpoint-at-x-after-the-star} Suppose a private vertex is contacted. Use some spare petals as star leaves, giving \(\ell\) additional contact edges. Neutralize every other touched petal by deleting its mate edge. Delete \(up_*,xq_*\), the \(\ell\) leaf edges and the ordinary preparations. Keep \(uq_*\), \(ux\) and \(uh\) when present. Choose \(k=1+\ell+o\) even; then \(u,x\) are both odd in \(J\). Every private vertex has at most its mate as an even neighbour, and the ordinary support vertices are witnesses as checked above. Every component avoiding \(h\) meets this support or contains \(x\); in the latter case a retained spoke supplies a private witness. Thus the decomposition of \(J\) uses at most \(m\) paths and has two endpoints at \(h\). After the regular \(BC\) restorations, let \(d=\mathcal D(u)\ge1\). Restore \(up_*\) towards \(p_*\), leaving \(d-1\) endpoints at \(u\), possibly zero. Apply the half-star to the remaining \(k-1\) contact edges. Every retained neighbour \(w\) has \(\mathcal D(w)\ge1\), including \(x\), \(h\) if present, and \(p_*\). The remaining star is odd, so the half-star subset has size \(a\ge k/2\). Its prospective final endpoint count is \((d-1)+2a-(k-1)=d+2a-k\ge1\). A pending private vertex has at most one neighbour \(w\) with \(\mathcal D(w)=0\) because \(\mathcal D(x)\ge1\) still holds; an ordinary leaf has at most two. Failure would therefore require every private leaf to be selected and \[ \ell+N-\epsilon\le1. \] The following choices contradict this inequality, except in the first row where the single remaining inward edge already finishes the star. {\def\LTcaptype{none} % do not increment counter \begin{longtable}[]{@{}lrr@{}} \toprule\noalign{} Case & \(\ell\) & \(\epsilon\) \\ \midrule\noalign{} \endhead \bottomrule\noalign{} \endlastfoot \(N=1\), type I, T1 or T2 & 0 & 0 \\ Odd \(N\ge3\) & 0 & 0 \\ Even \(N\), a spare single petal & 1 & 0 \\ Even \(N\ge4\), a T2 & 0 & 1 \\ \(N=2\), a T2 and a spare double petal & 2 & 1 \\ \end{longtable} } Restore the neutralized mate edges after the star, towards a contacted private vertex in each petal. Its retained neighbours \(u,x\) satisfy \(\mathcal D(u),\mathcal D(x)\ge1\). Then restore \(xq_*\) last towards \(q_*\). The donor has \(\mathcal D(x)\ge1\), and the recipient sees \(p_*\), whose endpoint count is at least two, and \(u\) if adjacent. All other retained neighbours are unchanged odd vertices, so input 4 applies to both restorations. The endpoint at \(x\) is spent only in this final step. \paragraph{\texorpdfstring{Using the endpoint at \(x\) before or during the star}{Using the endpoint at x before or during the star}}\label{using-the-endpoint-at-x-before-or-during-the-star} In the remaining \(N\ge2\) cases, \(N\) is even, there is no spare single petal, and either no T2 exists or \(N=2\) with no spare double petal. If \(ux\) exists, delete and prescribe it. Otherwise delete \(xq_*\) in a double petal when available, or in the sole single petal, for restoration before the star. Delete every private contact and use the special-T2 rule. A newly even \(u\) retains at most the even neighbour \(h\). The vertex \(x\) is odd. Each private vertex is either odd with at most one even neighbour or even with degree at most one in \(EV(J)\). When \(ux\) is absent and the spoke petal is double, both \(uq_*\) and \(xq_*\) are deleted, leaving \(q_*\) even with degree zero in \(EV(J)\). Every component avoiding \(h\) meets deletion support, whose ordinary and private vertices are witnesses. A component containing \(x\) has a private witness along a retained spoke, since \(r\ge2\) and at most one spoke was deleted. The decomposition of \(J\) therefore uses at most \(m\) paths and has \(\mathcal D(h)\ge2\). If \(ux\) is absent, first restore \(xq_*\) towards \(q_*\). Its mate and all its other retained neighbours are odd, so input 4 of Section 2 applies and gives \(q_*\) at least one endpoint. In a single petal \(q_*\) was odd in \(J\), so it now has at least two. After the regular \(BC\) restorations, apply the half-star. All pending leaves have at most two neighbours \(w\) with \(\mathcal D(w)=0\) and \(\sigma\ge1\). In a failure every double petal would have a selected private, since each of two pending mates would still have an endpoint at the other. There is at most one single petal. If \(ux\) is prescribed its contribution offsets a possible negative contribution from that petal. Otherwise the single petal is the spoke petal, and its mate has at least two endpoints after the early spoke restoration, forcing its contact to be selected in a failure. The windmill contribution is therefore nonnegative. The ordinary contribution is at least \(N-\epsilon\), so failure implies \[ N-\epsilon\le1-d_0. \] Since \(\epsilon\le d_0\), this contradicts \(N\ge2\). \paragraph{One three-contact triangle}\label{one-three-contact-triangle} The remaining case has \(N=1\) and type T3. Use \(uA\) as the reserved edge, delete \(BC\), and keep \(uh\) if present. Prepare the windmill by E1--E5. The vertices \(u,x,A,B,C\) are odd in \(J\). The private and ordinary support vertices are witnesses, and a retained spoke supplies one in a component containing \(x\). Thus the decomposition of \(J\) uses at most \(m\) paths and has \(\mathcal D(h)\ge2\). The extra deletion \(BC\) avoids \(u\) and the windmill. The conditions of Lemma 6.1 hold: \begin{itemize} \tightlist \item \textbf{(i)} The retained neighbours of \(u\) outside the windmill are \(B,C\), \(h\) if present, and unchanged odd vertices. \item \textbf{(ii)} The retained neighbours of \(A\) are \(B,C\) and unchanged odd vertices. \item \textbf{(iii)} Every vertex other than \(u\) that is odd in \(G\) and adjacent to a private vertex keeps its parity. \end{itemize} Lemma 6.1 gives \(\mathcal D(u)\ge1\), \(\mathcal D(A)\ge2\). Restore \(BC\) towards \(B\): its retained neighbours \(u,A\) satisfy \(\mathcal D(u),\mathcal D(A)\ge1\), and its other retained neighbours are unchanged odd vertices. This keeps \(\mathcal D(h)\ge2\). Every case contradicts the choice of \(G\). This proves Lemma 4.1. \(\square\) \section{8. A prescribed vertex with even neighbours}\label{a-prescribed-vertex-with-even-neighbours} Lemma 4.1 gives two endpoints at \(h\) when \(h\) is isolated in \(F\). If \(h\) has even neighbours, we delete all or all but one of the corresponding edges. In the second case we prescribe the other end of the retained edge in a smaller graph and then transfer endpoints back to \(h\). This is why the induction allows the prescribed vertex to change. Suppose Theorem 1.1 is false and choose a counterexample minimizing \((|V(G)|,|E(G)|)\), allowing the prescribed vertex to change in smaller instances. Corollary 3.2 makes its order even, say \(2m\). The other possible exception \(x\) is actual, since otherwise {[}FHZ{]} at \(h\) applies. The edge \(hx\) is absent by {[}X, Theorem 1.4{]}. Every star deletion below is centred at \(h\). Each deleted leaf \(w\) has \(d_F(w)\le3\), since \(hx\) is absent, so Lemma 2.4 applies throughout restoration. After deletion of the full star, every neighbour of \(h\) in \(G\) is odd. When one even-neighbour edge \(hv\) is retained, all other neighbours are odd and the smaller-instance theorem gives \(\mathcal D(v)\ge2\). Thus \(\mathcal D(w)\ge1\) at every neighbour required by the half-star input in both constructions. First consider a cut at \(h\). If components of \(G-h\) can be grouped into two nontrivial sides \(A,B\) with both \(d_A(h)\) and \(d_B(h)\) positive and even, apply a smaller instance of Theorem 1.1 to each side, or {[}FHZ{]} when the side has no \(x\). Every vertex other than \(h\) keeps its degree and parity, so each side meets the same degree condition in its even subgraph; both sides have fewer vertices. Obtain two paths ending at \(h\) on each side and join one pair of ending paths. At least two \(h\)-endpoints remain and the two ceilings minus one equal \(m\). If no such grouping exists, there are exactly two components with odd local \(h\)-degrees. An even-degree component would give a valid grouping, and four or more odd-degree components could be grouped two against the rest. Let the resulting sides be \(A\) of odd order and \(B\) of even order. If \(|B|\ge4\), attach a new leaf at \(h\) in \(A\), obtaining \(A'\). Its order is \(|A'|=2m+2-|B|<2m\), and the pendant restores \(h\)'s even parity, leaving the degree condition in the even subgraph unchanged. A smaller instance of Theorem 1.1, or {[}FHZ{]} when \(x\) is absent, gives a decomposition with \(\mathcal D(h)\ge2\) and at most \(\lceil |A'|/2\rceil=\lceil |A|/2\rceil\) paths. For \(B\), use the one-exception ceiling from {[}FHZ{]} at \(x\) if \(x\in B\), and input 1 of Section 2 otherwise. Here \(h\) is odd, so every even vertex other than \(x\) has at most three even neighbours. Trim the pendant using Lemma 2.5. If its path had at least two edges, at least three \(h\)-endpoints remain; join one to an endpoint in \(B\)'s decomposition. If the pendant was a one-edge path, deleting it saves one path and leaves at least one \(h\)-endpoint on the \(A\)-side. The vertex \(h\) is odd in \(B\), so its decomposition also supplies at least one endpoint at \(h\). Keep the two families unjoined: their endpoint counts at \(h\) add to at least two, and their path counts sum to at most \[ \left\lceil\frac{|A'|}{2}\right\rceil-1+ \left\lceil\frac{|B|}{2}\right\rceil=m, \] since \(|A|+|B|=2m+1\), with \(|A|\) odd and \(|B|\) even. The remaining case \(|B|=2\) makes \(B\) a single edge \(hw\). Then \(G-\{h,w\}=A-h\) is connected, since \(A-h\) is the other component of \(G-h\). For \(d_F(h)=0\), use Lemma 4.1. For odd \(d_F(h)>0\), delete the full even-neighbour star and call the resulting graph \(H\). Its centre \(h\) and all deleted leaves become odd; every vertex odd in \(G\) stays odd, and \(x\) keeps its parity. Thus \(x\) is the only possible exception in \(EV(H)\). If \(H\) is connected, its one-exception ceiling on all \(2m\) vertices gives at most \(m\) paths. Otherwise \(H\) consists of \(hw\) and the connected remainder of order \(2m-2\). The latter's one-exception ceiling uses at most \(m-1\) paths; the one-edge path \(hw\) brings the total to at most \(m\). In both cases Lemma 2.1 restores the odd star and gives \(\mathcal D(h)\ge2\), using Lemma 2.4. For positive even \(d_F(h)\), retain one edge \(hv\) to an even neighbour and delete the others. The resulting graph \(H\) is connected through \(hv,hw\), has fewer edges, and has \(h\) odd and \(v\) even and of positive degree. Every even vertex outside \(\{v,x\}\) has at most three even neighbours. Apply a smaller instance of Theorem 1.1 with \(v\) prescribed; then restore the odd missing star at \(h\). Its required neighbours each have an endpoint and its pending leaves have degree at most three in \(F\), leaving \(\mathcal D(h)\ge2\). Thus \(h\) is not a cut vertex in a minimum counterexample. The same three cases finish it. If \(d_F(h)=0\), Lemma 4.1 applies. Odd \(d_F(h)\) allows full-star deletion; a neighbour odd in \(G\) keeps the remaining graph connected, and the one-exception ceiling followed by odd-star restoration gives \(\mathcal D(h)\ge2\). Positive even \(d_F(h)\) allows the retained-edge deletion, which leaves a connected graph with fewer edges because \(h\) is not a cut vertex. Its retained neighbour \(v\) stays even and has positive degree, so a smaller instance of Theorem 1.1 and odd-star restoration apply. Every case is contradictory. This proves Theorem 1.1 and Corollary 1.2. \section{9. Scope}\label{scope} Theorem 1.1 prescribes two endpoints at one member of the pair at a time. At even order, obtaining them at both members in a common partition can require an extra path, as \(K_4\) minus an edge shows (Section 3). The endpoint conclusions concern at most two prescribed even vertices. Botler and Sambinelli prove that a connected simple graph \(G\) has a floor decomposition or is a SET graph whenever \(EV(G)\) is a subgraph of a graph whose blocks are subcubic and whose components are either subcubic or have at most one block containing a triangle {[}BS, Theorem 15{]}. The ceiling bound follows in either case. Take a tree \(T\) with three degree-four vertices and attach a new leaf to each odd-degree vertex of \(T\). The resulting graph \(G\) has \(EV(G)=T\), which satisfies the block condition and has at least three exceptions. The graph \(K_{2,4}\) satisfies the two-exception condition: every vertex is even and exactly two have degree four in \(F\). As a 2-connected graph of maximum degree four, it would lie in one block of any containing graph, preventing that block from being subcubic. Thus neither hypothesis implies the other. The unrestricted three-exception problem and Gallai's conjecture for a general connected graph remain open. \section{10. Formalization}\label{formalization} Palomar record PALOMAR-2026-10-04-000006, version 1 {[}P{]}, registers the Lean 4 formalizations of Theorem 1.1, Corollary 1.2, Proposition 3.1 and Corollary 3.2. The declared challenges in the namespace \texttt{Gallai.Submission} correspond to the manuscript as follows. {\def\LTcaptype{none} % do not increment counter \begin{longtable}[]{@{}ll@{}} \toprule\noalign{} Manuscript result & Lean declaration \\ \midrule\noalign{} \endhead \bottomrule\noalign{} \endlastfoot Theorem 1.1 & \texttt{prescribed\_endpoint} \\ Corollary 1.2 & \texttt{ceiling\_bound} \\ Proposition 3.1 & \texttt{simultaneous\_floor\_add\_one} \\ Corollary 3.2 & \texttt{odd\_order\_simultaneous} \\ \end{longtable} } \texttt{Challenge.lean} states these results using Mathlib's graphs and paths; \texttt{Solution.lean} proves them. The statements use nonempty simple paths and the same degree conditions, path budgets and endpoint counts as those above. The proofs depend only on \texttt{propext}, \texttt{Classical.choice} and \texttt{Quot.sound}. The registered proofs were accepted by Lean's kernel and by the independent NanoDa and con-ron checkers. The record preserves the source, pinned dependencies and verification evidence. \section{AI assistance}\label{ai-assistance} OpenAI Codex and other AI tools assisted with mathematical exploration, Lean formalization, and manuscript preparation. The author reviewed the AI-assisted material and takes full responsibility for the manuscript. \section{References}\label{references} {[}BS{]} F. Botler and M. Sambinelli, \emph{Towards Gallai's path decomposition conjecture}, Journal of Graph Theory 97 (2021), 161--184. \href{https://arxiv.org/abs/1911.04546}{Author version}. {[}FHZ{]} G.-H. Fan, J.-F. Hou and C.-X. Zhou, \emph{Gallai's Conjecture on Path Decompositions}, Journal of the Operations Research Society of China 11 (2023), 439--449. \href{https://doi.org/10.1007/s40305-022-00435-3}{Publisher}. {[}L{]} L. Lovász, \emph{On covering of graphs}, in \emph{Theory of Graphs} (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, 231--236. {[}Fan{]} G. Fan, \emph{Path decompositions and Gallai's conjecture}, Journal of Combinatorial Theory, Series B 93 (2005), 117--125. \href{https://doi.org/10.1016/j.jctb.2004.09.008}{Publisher}. {[}X{]} M. Xie, \emph{On Gallai's path decomposition conjecture}, Filomat 37:17 (2023), 5829--5834. \href{https://doi.org/10.2298/FIL2317829X}{DOI}. \href{https://www.pmf.ni.ac.rs/filomat-content/2023/37-17/37-17-23-19729.pdf}{Publisher manuscript}. {[}BBB{]} A. Blanché, M. Bonamy and N. Bonichon, \emph{Gallai's path decomposition in planar graphs}, arXiv:2110.08870 (2021; version 2, 2022). \href{https://arxiv.org/abs/2110.08870v2}{Author version 2}. {[}P{]} I. A. Shaik, \emph{Gallai's conjecture with two exceptional even vertices}, Palomar, PALOMAR-2026-10-04-000006, version 1 (2026). \href{https://palomar-registry.org/entry?id=PALOMAR-2026-10-04-000006&version=1}{Registered formalization}. \end{document}