Proof. Let \(v_1,\ldots,v_r\) be a longest path in \(F\). All neighbors of either end belong to the path. Suppose that \(r<\min\{|V(F)|,2d+1\}\). The two sets \[\{j\in\{1,\ldots,r-1\}:v_jv_r\in E(F)\},\qquad \{j\in\{1,\ldots,r-1\}:v_1v_{j+1}\in E(F)\}\] have at least \(d\) elements each, whereas their common index set has \(r-1\le 2d-1\) elements. Choose an index \(j\) in their intersection. If \(j=1\) or \(j=r-1\), the edge \(v_1v_r\) closes the path to a cycle. For \(2\le j\le r-2\), the two indicated edges instead give the cycle \[v_1,\ldots,v_j,v_r,v_{r-1},\ldots,v_{j+1},v_1\] through all vertices of the path. Thus in every case there is a cycle on these \(r\) vertices. Since \(r<|V(F)|\) and \(F\) is connected, some vertex outside the cycle has a neighbor on it. Starting with that vertex and then traversing the cycle with one edge omitted gives a longer path, a contradiction. ◻

Proof. Fix \(\chi\) and \(\ell\), and suppose that no such path exists. There are vertices \(y,z\) with \(\chi(y)\ne\chi(z)\) and a common neighbor \(x\). Indeed, if no such pair existed, the color would be preserved along every walk of length two. In a connected nonbipartite graph there is an even walk between any two vertices: if a connecting path has odd length, first insert an odd closed walk obtained by going to an odd cycle, traversing it, and returning. Preservation of the color along successive pairs of steps would make \(\chi\) constant. This proves the assertion, and \(x,y,z\) are distinct because the graph is simple.

Let \(K\) be the component containing \(x\) in \(H-\{y,z\}\). Every vertex of \(K\) loses at most two neighbors on deleting \(y,z\), and all its other neighbors lie in the same component. Thus \[ \delta(K)\ge s-2. \tag{10}\] There is no path of order at least \(\ell\) starting at \(x\) in \(K\). For the first \(\ell\) vertices of such a path form a path with some last vertex \(b\). At least one of \(y,z\) has color different from \(b\); prefixing that vertex gives a path of length \(\ell\) with differently colored ends.

Choose a longest path \(P\) starting at \(x\) in \(K\), and write \(W=V(P)\) and \(r=|W|\). All neighbors in \(K\) of its last vertex lie on \(P\), so (10) gives \(r\ge s-1\). If \(\ell\le s-1\), this already contradicts the preceding paragraph. This disposes in particular of \(\ell=1,2\). Henceforth we have \[ s\le\ell\le 2s-2, \qquad s-1\le r\le\ell-1. \tag{11}\]

The possible last vertices form a clique. Define \[E=\{e\in W:\text{there is a path from $x$ to $e$ whose vertex set is exactly $W$}\}.\] Every such path has the maximum possible order among paths starting at \(x\) in \(K\). Its last vertex has no neighbor in \(K-W\). Since vertices of \(K\) have no neighbors in \(H-(K\cup\{y,z\})\), we obtain \[ N_K(e)\subseteq W, \qquad N_H(e)\subseteq W\cup\{y,z\} \quad(e\in E). \tag{12}\] If two vertices of \(E\) were nonadjacent, their closed neighborhood in \(H\) would have size at most \(r+2\le\ell+1\le 2s-1\), contrary to the hypothesis. Thus \(E\) is a clique. Also \(x\notin E\), because a simple path with more than one vertex has distinct ends, and \(r\ge s-1\ge3\).

We use the standard fixed-end path rotation of Pósa (Pósa 1963, 358). The endpoint-clique and attachment conclusions needed here follow from our stated hypotheses. Explicitly, let \(v_1=x,\ldots,v_r=e\) be any path from \(x\) with vertex set \(W\). For an edge \(ev_j\) with \(1\le j\le r-2\), the sequence \[ v_1,\ldots,v_j,v_r,v_{r-1},\ldots,v_{j+1} \tag{13}\] is another path from \(x\) on exactly \(W\). Its last vertex is \(v_{j+1}\). The operation is valid also when \(j=1\), so the pivot may be \(x\). For \(j=r-1\), the original path itself has last vertex \(v_{j+1}=e\). Therefore the successor of every neighbor of \(e\) along the path belongs to \(E\). Different neighbors have different successors, and hence \[ d_K(e)\le |E| \qquad(e\in E). \tag{14}\] Combining (10) with the fact that \(E\) is a clique and \(H\) has no \(K_s\) gives \[ s-2\le |E|\le s-1. \tag{15}\]

On every path from \(x\) with vertex set \(W\), the vertices of \(E\) form a consecutive final segment. To see this, let \(e\) be its last vertex. Every earlier vertex of \(E\) is adjacent to \(e\), since \(E\) is a clique. The rotation then places its successor in \(E\) as well. Thus membership in \(E\) is preserved on moving forward along the path.

The endpoint clique attaches through one vertex. Fix one of the paths from \(x\) on \(W\). Let \(u\) be the predecessor of its final segment \(E\), and let \(w_0\) be the first vertex of that segment. Both are defined because \(E\) is nonempty and \(x\notin E\); in particular, \(u\notin E\) and \(uw_0\) is an edge.

For \(w\in E-\{w_0\}\), reorder the final clique segment so that it still starts at \(w_0\) and now ends at \(w\). Every neighbor of \(w\) in \(K\) lies on this path by (12), and the successor of each neighbor belongs to \(E\) by the rotation. A vertex of the prefix strictly before \(u\) has its successor outside \(E\), so it cannot be a neighbor of \(w\). Consequently \[ N_K(w)\subseteq (E-\{w\})\cup\{u\} \qquad(w\in E-\{w_0\}). \tag{16}\]

We claim that \(u\) has at least two neighbors in \(E\). There are two possibilities in (15). If \(|E|=s-2\), each \(w\in E-\{w_0\}\) has at most \((s-3)+3=s\) possible neighbors in \(H\): the other vertices of \(E\), and \(u,y,z\). Minimum degree \(s\) forces all these adjacencies. Since \(|E|\ge2\), there is such a \(w\), and \(u\) is adjacent to both \(w_0\) and \(w\).

If \(|E|=s-1\), suppose instead that \(w_0\) is the only neighbor of \(u\) in \(E\). By (16), every vertex in \(E-\{w_0\}\) must then see both \(y\) and \(z\) to have degree at least \(s\). The vertex \(w_0\) is itself a possible last vertex by the definition of \(E\), whether or not it is last in our fixed order. Thus (14) gives \(d_K(w_0)\le s-1\), so \(w_0\) sees at least one of \(y,z\). That vertex is adjacent to all of \(E\), giving a \(K_s\), a contradiction. We have proved the claim.

Choose a second neighbor \(w_1\in E-\{w_0\}\) of \(u\). Keeping the prefix through \(u\) fixed, we can enter \(E\) at \(w_1\) and reorder this clique so that \(w_0\) is last. The same successor argument used for (16) now applies to \(w_0\) as well. It follows that \[ N_K(E)\setminus E\subseteq\{u\}, \qquad |N_K(u)\cap E|\ge2. \tag{17}\]

There is a vertex \(w\in E\) adjacent to both \(y,z\). For \(|E|=s-2\), any vertex of \(E-\{w_0\}\) already has this property. For \(|E|=s-1\), suppose none does. Each vertex of \(E\) then has at most one neighbor among \(y,z\) and, by (17), no neighbor in \(K-E\) other than \(u\). To have degree at least \(s\), it must be adjacent to \(u\). Thus \(E\cup\{u\}\) would be a \(K_s\), again a contradiction.

A path starting in the endpoint clique is long enough. We now seek a path of order at least \(\ell\) starting at this vertex \(w\) in \(K\). Since both \(y\) and \(z\) are adjacent to \(w\), the same prefix argument used at \(x\) will give the final contradiction.

First, \(K\) is not a clique. Its minimum degree would force a clique \(K\) to have at least \(s-1\) vertices. It cannot have at least \(s\) vertices, and if it has exactly \(s-1\), minimum degree \(s\) in \(H\) forces every vertex of \(K\) to see both \(y,z\). Then \(K\cup\{y\}\) is a \(K_s\). Hence \(K\) has a nonadjacent pair. Its closed neighborhood in \(H\) is contained in \(K\cup\{y,z\}\), so the independent-pair hypothesis gives \[ |V(K)|\ge 2s-2. \tag{18}\]

The graph \(K-E\) is connected. Otherwise, since \(K\) is connected, each component of \(K-E\) would have a neighbor in \(E\); (17) would force every one of these components to contain \(u\). Moreover, \[|V(K-E)|\ge (2s-2)-(s-1)=s-1\ge3.\] Let \(R\) be a longest path starting at \(u\) in \(K-E\), and let \(v\) be its last vertex. Connectedness and the preceding size bound ensure that \(R\) is nontrivial, so \(v\ne u\). By (17), the vertex \(v\) has no neighbor in \(E\); by maximality of \(R\), all its neighbors in \(K-E\) lie on \(R\). Thus all its neighbors in \(K\) lie on \(R\), and \[ |V(R)|\ge d_K(v)+1\ge s-1. \tag{19}\]

If \(|E|=s-2\) and \(|V(R)|=s-1\), the vertices \(v,w\) are nonadjacent by (17), since \(v\ne u\). Their closed neighborhood in \(H\) is contained in \[E\cup V(R)\cup\{y,z\}.\] These sets are disjoint and have total size \((s-2)+(s-1)+2=2s-1\), contrary to the hypothesis. Together with (15) and (19), this proves \[|E|+|V(R)|\ge2s-2\ge\ell.\]

By (17), choose a neighbor \(e\) of \(u\) in \(E\) different from \(w\). Traverse all of the clique \(E\) in a path starting at \(w\) and ending at \(e\), follow the edge \(eu\), and then follow \(R\) from \(u\), as shown in Figure 1. The vertex sets \(E\) and \(V(R)\) are disjoint, so this is a simple path in \(K\) of order \(|E|+|V(R)|\ge\ell\) starting at \(w\). Take its first \(\ell\) vertices and prefix whichever of \(y,z\) has color different from its last vertex. The prefixed vertex lies outside \(K\), so the resulting path is simple and has length exactly \(\ell\). This contradicts the choice of \(\ell\) and completes the proof. ◻

Proof of Theorem 4. Lemma 5 gives \(3\le t\le k\). If \(s=\lfloor k/2\rfloor\le3\), this is the required bound. Suppose therefore that \(s\ge4\) and that \(G\) has no \(K_s\). Choose a vertex of \(G\) and a breadth-first spanning tree of its component rooted at that vertex. Since \(\alpha(G)\le a\le k\), Proposition 6 applies and gives \(H\) in one distance layer \(D_i\) of this tree, where \(1\le i\le s\).

In the breadth-first tree defining this layer, let \(c\) be the lowest common ancestor of all vertices of \(H\). They all have depth \(i\), so their distance below \(c\) is the same integer \[p=i-\operatorname{depth}(c).\] The graph \(H\) has at least \(k\) vertices, so \(c\) is a proper ancestor of its vertices, giving \(1\le p\le i\le s\). At least two child branches of \(c\) meet \(H\), since otherwise the common child would be a lower common ancestor.

If \(p=1\), every vertex of \(H\) is adjacent to \(c\). By Lemma 7, the graph \(H\) contains a path of order at least \[\min\{|V(H)|,2s+1\}\ge k,\] because \(|V(H)|\ge k\) and \(k\in\{2s,2s+1\}\). Take a subpath of order exactly \(k\) and join both ends to \(c\). The vertex \(c\) lies above \(D_i\), so this gives a simple cycle of order \(k+1\), a contradiction.

Suppose that \(p\ge2\). Partition the child branches of \(c\) that meet \(H\) into two nonempty classes, and color each vertex of \(H\) according to its class. This is a nonconstant coloring. Vertices of different colors have tree distance exactly \(2p\), and all internal vertices of their tree path have depth less than \(i\). Set \[\ell=k+1-2p.\] The inequalities \(p\le s\), \(p\ge2\), and \(k\in\{2s,2s+1\}\) give \(1\le\ell\le2s-2\). The graph \(H\) has all the hypotheses of Lemma 8: its independent-set neighborhood bound applies in particular to independent pairs. That lemma supplies a path in \(H\) of length exactly \(\ell\) with differently colored ends. Its vertices have depth \(i\), so its interior is disjoint from the tree path between its ends. The union of the two paths is therefore a simple cycle of length \[\ell+2p=k+1.\] This final contradiction proves \(t\ge s\) and hence the theorem. ◻

Proof. Suppose such a system exists. The integer \[u=k+1-q-v\] satisfies \(0\leq u\leq t-v\): the first inequality follows from the upper bound on \(q\), and the second from \(q\geq h\). Choose exactly \(u\) of the clique vertices not incident with represented edges.

Expand each nontrivial chain by replacing its represented edges with their assigned paths. Each expansion is a simple path, and different expansions are vertex-disjoint. Indeed, their clique vertices belong to different forest components, and all assigned interiors are disjoint and lie outside \(Q\). Adjoin the \(u\) chosen unused clique vertices as singleton paths. These paths together contain exactly \[q+v+u=k+1\] vertices, and all their endpoints belong to \(Q\).

There is at least one nontrivial expanded chain, since \(q\geq h\geq1\). If there is only one path in the resulting list, it has at least three vertices: it contains an assigned path with nonempty interior. The clique edge between its distinct endpoints closes it into a simple cycle. If there are two or more paths, order and orient them arbitrarily, join each path’s last endpoint to the next path’s first endpoint by a clique edge, and close the last to the first. This again gives a simple cycle. In the case of two paths with one singleton, the two joining edges use the two distinct endpoints of the nontrivial path; thus they are distinct. The case of two singleton paths cannot occur. All remaining cases follow directly from vertex-disjointness. The resulting cycle has order \(k+1\), a contradiction. ◻

Proof. If \(A\geq h\), Lemma 13 applies. If \(A<h\) and \(e'\geq e\), the lower bound gives \(A\geq L+1\), contrary to the maximality of \(L\). If \(A<h\) and \(e'<e\), that lower bound gives \(A\geq L\). Strict inequality again contradicts maximality, and equality contradicts the choice of \(e\). ◻

Proof. A vertex of \(S\) has at most \(|S|-1\) neighbors in \(S\) and has degree at least \(k\). Now use (27). ◻

Proof. If the two balls in the first assertion meet, concatenate their paths from \(x\) and \(y\) to a common vertex. This gives an \(x\)–\(y\) walk of at most \(r+s+2\) edges, all of whose internal vertices lie outside \(X\). Deleting repeated portions produces a simple outside path with at most \(r+s+1\) internal vertices. If instead an edge joins the two balls, use that edge between the two paths. The resulting walk has at most \(r+s+3\) edges and yields an outside path with at most \(r+s+2\) internal vertices. In both cases the parameter is at least one, since the walk has no direct step from \(x\) to \(y\). Each case contradicts the hypothesis.

For the second assertion, a vertex of \(B_{r-1}(x;X)\) has a path from \(x\) of at most \(r\) edges with all subsequent vertices outside \(X\). If that vertex were adjacent to \(y\), appending the edge to \(y\) would give an outside path with between one and \(r\) internal vertices. ◻

Proof. The case of two singletons is immediate, and the case \(r,s\geq0\) is Lemma 16. It remains to consider \(r=-1\) and \(s\geq0\), after interchanging the options if necessary. The singleton \(\{x\}\) and the ball \(B_s(y;X)\) are disjoint because they lie in \(X\) and \(V(G)\setminus X\), respectively. An edge between them would give an outside \(x\)–\(y\) path with between one and \(s+1=r+s+2\) internal vertices, contrary to the hypothesis. ◻

Proof. If \(L+d<h\), then \(\mathcal R\) contradicts the maximality of \(L\). Otherwise choose an inclusion-minimal subcollection of \(\mathcal R\) with amount at least \(h\). Write its amount as \(h+j\), its number of paths as \(r\), and its number of incident clique vertices as \(w\). The subcollection contains the new path, since the old paths have total amount \(L<h\). Also \[0\le j\le5,\] because \(h+j\le L+d\le h+5\). Lemma 13 gives \[h+j>k+1-w,\qquad\text{or equivalently}\qquad w>t-j.\] Since \(w\le t\), this also excludes \(j=0\). Thus \[ 1\le j\le5,\qquad 2r\ge w\ge t-j+1. \tag{33}\]

Deleting any selected path lowers the amount below \(h\); consequently every selected amount is at least \(j+1\). Suppose that all were at least \(j+2\). Exactly \(r-1\) of the selected paths are old, so \[(r-1)(j+2)\le L\le k-t.\] Together with (33), this implies \[(t-j-1)(j+2)\le2(k-t)\le2t+2.\] The left side is a concave function of \(j\) on \([1,5]\). Its endpoint values are \(3(t-2)\) and \(7(t-6)\), whose differences from \(2t+2\) are respectively \(t-8\) and \(5t-44\). Both are positive for \(t\ge9\), a contradiction.

Some selected path therefore has amount exactly \(j+1\). Deleting it, whether it is old or new, leaves a valid system of amount \(h-1\). Maximality gives \(L=h-1\). The minimum-path tie-break in the choice of \(\mathcal P\) now gives \(r-1\ge e\). On the other hand, \(\mathcal R\) has at most \(e+1\) paths, so \(r\le e+1\). Hence \(r=e+1\): the selected subcollection is all of \(\mathcal R\), and all old paths occur in it. Comparing its two expressions for the total amount gives \[h+j=L+d=h-1+d,\qquad j=d-1.\] Thus every selected amount is at least \(j+1=d\), and, since all old paths remain, the new path has amount exactly \(d\). ◻

Proof. Lemma 18 constructs a valid system of amount \(L+d\), consisting of unchanged old paths and one new path. Lemma 22 shows that no old path was removed. The two targets must therefore be starting vertices, and every old amount is at least \(d\). The proof of Lemma 22 also gives \(j=d-1\ge1\), so \(d\ge2\).

Let \(a\in\{0,1,2\}\) be the number of missing targets among these two vertices. The new system has exactly \(v+a\) incident vertices. Its amount is \(h+d-1\); hence Lemma 13 gives \[ v+a\ge t-d+2. \tag{34}\] In particular, \(v\ge t-d\). Since \(v\le2e\) and every old amount is at least \(d\), we obtain \[ 2\le d\le6,\qquad d\left\lceil\frac{t-d}{2}\right\rceil \le de\le L=k-t\le t+1. \tag{35}\]

For \(d=2\), this gives \(v\ge t-2\). Equation (34) says that \(v+a\ge t\), so the two targets must cover all \(t-v\) missing vertices.

For \(d=3\), dropping the ceiling in (35) gives \(3(t-3)\le2(t+1)\), and hence \(t\le11\). At \(t=10\), the exact bound fails because \(3\lceil7/2\rceil=12>11\). At \(t=9\) it forces \(e=3\), and at \(t=11\) it forces \(e=4\). In each case \[t-3\le v\le2e=t-3.\] Thus \(v=2e=t-3\), so no two old edges share a clique vertex. Equation (34) then forces \(a=2\).

For \(d=4\), the weaker bound \(4(t-4)\le2(t+1)\) gives \(t\le9\); but at \(t=9\) the exact bound fails: \(4\lceil5/2\rceil=12>10\). For \(d=5\), the weaker bound gives \(3t\le27\), hence \(t=9\). Now \(2\le e\le2\) and \(4\le v\le2e=4\). Moreover, \[10=5e\le L\le t+1=10,\] so \(L=10\), \(k=19\), and both amounts are five. Again (34) forces \(a=2\). Finally, for \(d=6\), the weaker bound gives \(4t\le38\), hence \(t=9\); there \(6\lceil3/2\rceil=12>10\), which is impossible.

The three surviving alternatives are mutually exclusive properties of the fixed old system: they require respectively \[v\ge t-2,\qquad v=t-3,\qquad t=9,\ v=t-5.\] The argument applies to every orientation and every pair admitting a path with parameter between one and six. Thus, once the old system lies in one alternative, any such path in any orientation must obey the corresponding parameter and endpoint restrictions. ◻

Proof. The matching in Alternative [terminal:three] has three or four edges, and that in Alternative [terminal:five] has two. In Alternative [terminal:two], if there were only one nonsingleton chain, then \[v=e+1\le\left\lfloor\frac{t+1}{2}\right\rfloor+1<t-2,\] contrary to \(v\ge t-2\). Here \(2e\le L\le t+1\) was used. There cannot be no nonsingleton chain, since \(v\ge t-2>0\).

Fix an orientation in which \(x\) is a representative. Choose a nonsingleton chain other than the chain containing its target, and reverse only that chain. Its old terminal clique vertex becomes a representative, although it was not one of the original representatives; meanwhile \(x\) remains a representative. By Lemma 19, every vertex of \(B_0(x;S)\) is nonadjacent to the other \(t-1\) original representatives and to this additional clique vertex.

Lemma 23 gives \(|S|=t+L=k\). The set \(B_0(x;S)\) is nonempty, because \(\delta(G)\ge k\) and \(|S|\le k\). For \(z\in B_0(x;S)\), its closed neighborhood has size at least \(k+1\), meets \(S\) in at most \(|S|-t\) vertices, and is contained in \(S\cup B_1(x;S)\). Therefore \[|B_1(x;S)|\ge k+1-(|S|-t)=t+1.\] Since \(t\) is the maximum clique size, this ball contains an independent pair \(I\). The expansion inequality (3) and the containment \(N_G[I]\subseteq S\cup B_2(x;S)\) give \[|B_2(x;S)|\ge2k+1-|S|=k+1.\] If \(k\ge2t\), this exceeds \(\max(k,2t)\), so Lemma 12 supplies an independent triple. ◻

Proof. By Lemma 21, some pair of representatives admits an outside path with parameter between one and six. We may therefore apply Lemma 23. In each of its alternatives we will choose balls with distinct bases that are pairwise disjoint and anticomplete. Independent sets in these balls then combine into an independent set in \(G\).

Proof. An isomorphism of two nontrivial paths either preserves or reverses their endpoint order. Therefore their weighted isomorphism classes agree exactly when their amount tuples agree up to reversal. A forest isomorphism permutes components and acts in this way within each one. Reversal normalization followed by sorting consequently gives a complete invariant, with multiplicities preserved.

Every candidate first tuple is obtained by listing positive integer compositions of each amount from zero to \(B\), restricting the number of entries to at most \(t-1\). The amount-zero candidate is just the empty tuple. For example, one may start with the empty tuple and repeatedly append a positive integer no larger than the remaining budget. Each tuple is reached once. Normalization and the lower bound are tested when selecting a component; a rejected prefix must still be extended, since a longer tuple can satisfy these conditions even when its prefix does not.

Now induct on \(t\). For \(t=0\) the empty list is the unique pattern, regardless of unused budget. For \(t>0\), the first tuple consumes \(\ell(p)+1\ge1\) vertices and \(\sigma(p)\) amount. The inductive hypothesis supplies every allowed tail exactly once, while its lower bound \(p\) enforces nondecreasing order. Conversely, every permitted list has exactly this first tuple and one of these tails. This proves both coverage and uniqueness. ◻

Proof. A component tuple \(p\) occupies exactly \(\ell(p)+1+\sigma(p)\) consecutive labels. Its successive expanded paths share their common clique endpoint and have disjoint interiors. Different components occupy disjoint intervals of labels. Summing these facts gives the asserted counts and the unique interval for each interior vertex, including when some or all components are singletons.

Within a component, the clique labels strictly increase along the path; all labels of an earlier component precede those of a later one. A subset of the old edges is a union of subpaths of these components. Its unique route between connected labels \(z<w\) therefore traverses increasing labels, and these edges appear in the same order in \(\mathcal E(P)\). ◻

Proof. Suppose such an outside path exists. Extend its end \(x\) to \(z\) along the old path containing \(x\), or use the singleton segment \(\{x\}\) if \(x\in Q\). Extend its other end from \(y\) to \(w\) in the same way. Each extension meets \(Q\) only at its chosen endpoint.

We first check that these two extension segments are disjoint. If both are nontrivial and supported on the same old path with endpoints \(a<b\), the conditions \(x<y\) and \(z<w\) force \(z=a,w=b\). The two segments then have vertex sets \(\{a,\ldots,x\}\) and \(\{y,\ldots,b\}\), which are disjoint. If their supporting old paths are different, their interiors are disjoint, so an intersection could only be their common chosen clique endpoint. This would give \(z=w\), contrary to the choice. If one segment is a singleton in \(Q\), it likewise can meet the other segment only at that segment’s chosen clique endpoint, again excluded. Two singleton segments are disjoint because \(x<y\).

The assumed outside path has all its internal vertices outside \(S\). Concatenating it with the two disjoint extension segments therefore gives a simple \(z\)-\(w\) path whose interior lies outside \(Q\). It has \[d+|x-z|+|y-w|\] internal vertices: when \(x\notin Q\), the first extension contributes all its vertices except \(z\), including \(x\), and similarly at \(y\). In particular its amount is positive.

Every old path containing \(x\) or \(y\) in its interior must be discarded, because that vertex is internal to the new path. These are exactly the old paths whose interiors can meet an extension. If \(x,y\) lie on the same old path it is discarded only once. Consequently the new path and all the old paths represented by \(E\) have pairwise disjoint interiors. Taking a subset of the remaining old paths only discards more paths and preserves this property.

The endpoint graph \(E\) is already a linear forest. Adding \(zw\) keeps every degree at most two, by the degree assumptions, and creates no cycle, because \(z,w\) were in different components. This condition also prevents a repeated endpoint edge. Hence the old paths represented by \(E\), together with the new path, form an admissible system with \(e'\) paths, \(v'\) incident clique vertices, and amount \[A=q+d.\] The lower bound in (42) says that \(A\ge L+1\) when \(e'\ge e\), and \(A\ge L\) when \(e'<e\). If \(A<h\), it contradicts maximality of \(L\), or, in the case \(A=L\) and \(e'<e\), the minimum-path tie-break. If \(A\ge h\), the upper bound gives \[h\le A\le k+1-v',\] contrary to Lemma 13. Since \(L<h\), these alternatives cover the entire stated interval. ◻

Proof. If an outside path with \(d=k-\ell\) internal vertices existed, it would have length \(d+1\). Its interior is disjoint from the required path, since the latter lies wholly in \(X\). Their union is therefore a simple cycle of length \[\ell+(d+1)=k+1.\] For \(d=0\), the outside path is the edge \(xy\) and the required path has length \(k\ge5\), so the same conclusion holds without any repeated edge. Additional edges of \(G\) may be chords of this cycle and do not affect the contradiction. ◻

Proof. An outside path relative to \(X'\) has all its internal vertices in \(V(G)\setminus X'\subseteq V(G)\setminus X\), so it is also an outside path relative to \(X\). This includes parameter \(0\), for which the interior is empty. ◻

Proof. The empty diagonal means that the vertices counted by \(|\{j:0\in M_{ij}\}|\) are all distinct from \(i\). They are nonneighbors of \(i\). Thus at most \(n_X-1-|\{j:0\in M_{ij}\}|\) neighbors of \(i\) lie in \(X\), proving the bound on \(|B_0(i;X)|\). Positivity gives an independent vertex. Furthermore, a \(t\)-clique in \(B_0(i;X)\) together with \(i\) would be a \((t+1)\)-clique. Therefore \(b_0\ge t\) forces an independent pair, which proves the asserted value of \(u_0\).

Suppose the bounds have been proved at radius \(r-1\). Each vertex \(j\in A_r(i)\) is distinct from \(i\), because \(M_{ii}\) is empty, and has no neighbor in \(B_{r-1}(i;X)\). Indeed, such a neighbor would give an outside \(i\)–\(j\) path with between one and \(r\) internal vertices, by the no-neighbor assertion of Lemma 16. Choose an independent set \(I\subseteq B_{r-1}(i;X)\) of order \(u_{r-1}\). Its closed neighborhood outside \(X\) is contained in \(B_r(i;X)\), whereas its closed neighborhood inside \(X\) avoids the \(T_r\) vertices of \(A_r(i)\). Expansion gives \[|B_r(i;X)|\ge ku_{r-1}+1-(n_X-T_r).\] The balls are nested, so (44) follows. Nesting also preserves the independence bound \(u_{r-1}\). If \(b_r>t\), the ball is not a clique; if \(b_r>\max(k,2t)\), Lemma 12 supplies an independent triple. These are precisely the additional bounds in (45), with the stated strict inequalities.

It remains to justify (46). If \(B_r(i;X)\) were a clique \(C\), nesting and \(b_{r-1}=b_r=t\) would force \[B_{r-1}(i;X)=B_r(i;X)=C,\qquad |C|=t.\] Every \(v\in C\) has at most \(t-1\) neighbors outside \(X\), since \(B_r(i;X)\) contains all outside neighbors of the preceding ball. The vertices of \(A_r(i)\) are also unavailable as neighbors. Hence \[k+1-t \ \le\ |N_G(v)\cap X| \ \le\ n_X-T_r \ \le\ k+1-t.\] If the last inequality were strict, there would already be a contradiction. Otherwise equality forces \(v\) to be adjacent to every vertex of \(X\setminus A_r(i)\), including \(i\). Thus \(C\cup\{i\}\) is a \((t+1)\)-clique, a contradiction. The ball therefore contains an independent pair. ◻

Proof. For \(r,s\ge0\), the balls are disjoint and anticomplete by Lemma 16. For a singleton \(\{i\}\) and a ball \(B_s(j;X)\), disjointness is automatic. An edge between them would give an outside \(i\)–\(j\) path with between one and \(s+1\) internal vertices, which is prohibited by (47) with \(r=-1\). Two singleton options are nonadjacent precisely when their joining edge is absent, as certified by \(0\in M_{ij}\). Thus all represented sets are disjoint and pairwise anticomplete. Independent subsets of their certified weights combine into an independent set in \(G\). Its order cannot exceed \(k\). ◻

Proof. Assume an outside \(i\)–\(j\) path with parameter \(d\) exists relative to \(S\). For \(d=0\) it is the edge \(ij\), so the trial required-edge graph is realized on \(S\). For \(d=1\), choose its actual internal vertex \(z\notin S\). The trial required-edge graph is then realized on \(S\cup\{z\}\). There may be other edges involving \(z\); the required graph does not assert their absence.

In both cases, every old forbidden parameter remains valid on \(X\) by Lemma 31: restricting the allowed outside vertices cannot create a previously forbidden path. The additional required-path constraints are valid by Lemma 30. Either stipulated contradiction is therefore impossible in this realization. This excludes the assumed path. In the case \(d=1\), the argument applies to any actual choice of its internal vertex, so the conclusion is a prohibition relative to the original set \(S\), not merely to one enlarged trial set. ◻

Proof. Suppose such a realization exists. Its initial forbidden parameters are valid by Lemma 29, and the constraints added in Step 2 are valid by Lemma 30. Inductively assume the current matrix contains valid prohibitions. Each new entry collected in Step 3 follows from that same matrix by Lemma 34. Every collected prohibition therefore holds in the realization, and they may all be added simultaneously. No new entry has been assumed in proving another entry of its batch. This proves the invariant at every subsequent step. An immediate required-edge contradiction or a violation of Lemma 33 is thus impossible, proving the assertion about outputs \(1\) and \(2\).

Every pass through Step 4 that does not terminate adds a previously absent parameter from the finite set of \(2\binom{|S|}{2}\) pair-and-parameter choices. The procedure must therefore terminate. Its soundness does not require that the two tests detect every possible obstruction to a realization. ◻

Proof of Proposition 26. Suppose such a graph exists and choose an optimal path system on a maximum clique. Lemma 27 places its pattern in the enumerated list. Lemma 28 gives its required-edge representation. All assumptions used by the procedure hold: the expansion and clique bounds are hypotheses of the proposition, the size test follows from Lemma 12, and optimality gives Lemma 29. Proposition 35 therefore applies. Table 2 records output \(1\) or \(2\) for every enumerated pattern, each of which contradicts the supposed realization. This proves the proposition. ◻

Proof of Theorem 1. First suppose \(m\ge n\ge3\) and \((m,n)\ne(3,3)\). Then \(m\ge4\), so \(k=m-1\ge3\), and \(2\le n-1\le k\). If the upper bound failed, choose the least failed independence parameter as in Section 2. The resulting graph \(G\) has no \(C_{k+1}\), satisfies \(\alpha(G)\le k\), and has the expansion property of Lemma 3. Theorem 4 gives \(\max\{3,\lfloor k/2\rfloor\}\le t=\omega(G)\le k\). Proposition 9 rules out \(k=3,4\). For \(k\ge5\), Proposition 25 rules out \(t\ge9\). The remaining values satisfy (36), so Proposition 26 rules them out as well. This proves the upper bound.

For the lower bound, colour the edges within each of \(n-1\) disjoint sets of size \(m-1\) red and all edges between sets blue. A red connected graph lies in a single set and hence cannot be a \(C_m\). A blue clique uses at most one vertex from each set and hence has order at most \(n-1\). This colouring has \((m-1)(n-1)\) vertices, proving the matching lower bound.

Finally, colour the edges of a \(5\)-cycle red and its complementary \(5\)-cycle blue. This gives \(R(C_3,K_3)\ge6\). In a two-colouring of \(K_6\), one vertex has at least three neighbours of one colour, say red. Any red edge among those neighbours completes a red triangle; if there is none, the three neighbours form a blue triangle. Thus \(R(C_3,K_3)=6\). ◻