Cycle–clique Ramsey numbers

Proof. If b=0, the graph H is empty, since any vertex would be an independent set of order one. If b=1, the graph is complete. A complete graph with at least k+1 vertices contains a cycle of exactly k+1 vertices, so in this case |V(H)|\le k.

Now let 2\le b<a. If |V(H)|\ge kb+1, take an induced subgraph on kb+1 vertices. It still contains no C_{k+1} and has independence number at most b. It would therefore be a counterexample for the smaller parameter b, contrary to the choice of a.□

Proof. Put r=|I|, so that 1\le r\le a. Every independent set in G-N_G[I] can be adjoined to I, because it has no edges to I. Consequently,

The integer a-r lies between zero and a-1. The graph G-N_G[I] also contains no C_{k+1}, so Lemma 2.1 applies, including when r=a, and gives

Subtracting from |V(G)|=ka+1 proves (2.2). Applying the bound to I=\{x\} yields d_G(x)+1\ge k+1, and hence \delta(G)\ge k. Finally, \alpha(G)\le a\le k by the choice of the parameters.□

Proof. A clique on k+1 vertices contains a C_{k+1}, so t\le k. For the other inequality, put r_b=R(K_3,K_b). The elementary Ramsey recurrence gives

Indeed, in a graph on b+r_{b-1} vertices, choose a vertex v. If v has at least b neighbors, either two of them are adjacent, giving a triangle, or there is an independent set of size b. Otherwise v has at least r_{b-1} nonneighbors; among them there is a triangle or an independent set of size b-1, to which v can be added. Induction gives the displayed bound on r_b.

Since a\le k and k\ge3, we have a+3\le2k, and hence

The alternative of an independent set of size a+1 is excluded, so G contains a triangle.□

Proof. Let D_j be the set of vertices at distance j from r. These are exactly the depth layers of T. Layers beyond the maximum depth are empty, and we use \alpha(\varnothing)=0. Every edge in the root component joins layers whose indices differ by at most one. Thus maximum independent sets chosen in layers of one parity can be united, giving an independent set of size

In particular p_i\le k and p_0=1. Applying expansion to a singleton gives \delta(G)\ge k, so D_1\ne\varnothing. Consequently every union defining p_i is nonempty: it contains either the root or an independent vertex from D_1.

For 1\le i\le s, the closed neighborhood of the independent union defining p_{i-1} is contained in D_0\cup\cdots\cup D_i. No vertex in another component is adjacent to this union. Expansion and |D_0|=1 give

Also, the two parity sums partition the indices from zero through i, so

Suppose first that k=2s. If every nonempty layer D_j, 1\le j\le s, satisfied |D_j|<s\alpha(D_j), then (3.3) and (3.4) would imply

The strict inequality holds even when some layers are empty, since every sum contains the nonempty layer D_1. It follows that p_i>p_{i-1}+1, and therefore, by integrality, p_i\ge p_{i-1}+2. Iterating to i=s gives p_s\ge2s+1>k, a contradiction. Hence some nonempty layer D_i, 1\le i\le s, satisfies

Now suppose that k=2s+1. If |D_j|\le s\alpha(D_j) for every 1\le j\le s, including empty layers, the same two identities give

Starting from p_0=1, each increment is at least two, so p_{s-1}\ge2s-1>s. The last increment is consequently at least three, giving p_s\ge2s+2>k, again a contradiction. Thus some layer D_i, 1\le i\le s, satisfies

This layer is necessarily nonempty.

We have found a layer of sufficiently large order relative to its independence number. Choose within it a nonempty induced subgraph H of minimum order satisfying the corresponding inequality (3.5) or (3.6). Since G has no K_s, such an H cannot be complete: a complete graph satisfying either inequality would have at least s vertices. Thus \alpha(H)\ge2. For even k this gives |V(H)|\ge2s=k; for odd k it gives |V(H)|>2s, hence |V(H)|\ge2s+1=k.

The graph H is connected. Otherwise each component H_j would be a proper nonempty induced subgraph and would fail the chosen inequality. Since independence number is additive across components, summing these failures would give

contrary to its choice. Nor is H bipartite: a bipartition would give \alpha(H)\ge |V(H)|/2, incompatible with |V(H)|\ge s\alpha(H) and s\ge4.

Let I be a nonempty independent set in H, and put R=H-N_H[I]. An independent set in R can be united with I, so

If R\ne\varnothing, minimality gives |V(R)|<s\alpha(R) for even k, and |V(R)|\le s\alpha(R) for odd k. Comparing with the defining inequality for H, one comparison is strict in each parity. Therefore

If R=\varnothing, instead use |N_H[I]|=|V(H)|\ge s\alpha(H)\ge s|I|; the first inequality is strict for odd k.

Finally, take I=\{v\}. When H-N_H[v] is nonempty, the strict neighborhood bound gives d_H(v)+1>s, hence d_H(v)\ge s. When it is empty, the order bound gives d_H(v)=|V(H)|-1\ge k-1\ge s. This proves all the asserted properties of H.□

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

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

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

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 (3.7) 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

The possible last vertices form a clique. Define

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

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 [12, p. 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

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

Combining (3.7) with the fact that E is a clique and H has no K_s gives

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 (3.9), 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

We claim that u has at least two neighbors in E. There are two possibilities in (3.12). 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 (3.13), 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 (3.11) 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 (3.13) now applies to w_0 as well. It follows that

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 (3.14), 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

The graph K-E is connected. Otherwise, since K is connected, each component of K-E would have a neighbor in E; (3.14) would force every one of these components to contain u. Moreover,

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 (3.14), 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

If |E|=s-2 and |V(R)|=s-1, the vertices v,w are nonadjacent by (3.14), since v\ne u. Their closed neighborhood in H is contained in

These sets are disjoint and have total size (s-2)+(s-1)+2=2s-1, contrary to the hypothesis. Together with (3.12) and (3.16), this proves

By (3.14), 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 3.1. Lemma 3.2 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 3.3 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

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 3.4, the graph H contains a path of order at least

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

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 3.5: 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

This final contradiction proves t\ge s and hence the theorem.□

Proof. Suppose such a graph exists. Applying the neighborhood bound to a singleton gives \delta(G)\ge k. Lemma 3.2 supplies a triangle, and a clique of order k+1 would contain the forbidden cycle, so 3\le\omega(G)\le k.

For a clique Q=\{q_1,\ldots,q_t\}, let F=G-Q and put

We will use this notation with different choices of Q, specifying the choice each time. A path between two distinct vertices of Q whose internal vertices lie in F can be completed using edges of Q. The exact numbers of internal vertices that are forbidden are checked below.

The case k=3. Choose a triangle Q=\{q_1,q_2,q_3\}. Each U_i is nonempty, since q_i has two neighbors inside Q and degree at least three. For distinct i,j, write h for the remaining index. A common vertex u\in U_i\cap U_j would give the cycle

of order four. If u\in U_i and v\in U_j were adjacent, then

would be a cycle of order four. Thus the sets U_1,U_2,U_3 are pairwise disjoint and pairwise anticomplete.

Choosing one vertex from each U_i gives an independent set of order three. Hence a=3. If any U_i contained two nonadjacent vertices, adjoining one vertex from each of the other two sets would give an independent set of order four. Therefore each U_i is a clique. Moreover, \{q_i\}\cup U_i is a clique and there is no K_4, so

Since |V(F)|=7, the set

is nonempty. Every vertex of W has no neighbor in Q by the definition of the U_i.

Fix w\in W. If w saw two distinct vertices u,v\in U_i, then w,u,q_i,v,w would be a C_4. Thus w has at most one neighbor in each U_i. On the other hand, if w missed a vertex u\in U_i and a vertex v\in U_j for distinct i,j, then \{w,u,v,q_h\} would be an independent set of order four. Indeed, w misses Q, the two exterior sets are anticomplete, and q_h has no neighbor in either of them. It follows that w is adjacent to every vertex of at least two of the U_i. These two sets must therefore be singletons.

There are consequently at least two singleton sets among the three U_i. If exactly two are singletons, the three sizes are 1,1,2, so |W|=3. Every vertex of W sees the two singleton vertices, say u,v. Distinct w,w'\in W then give the cycle w,u,w',v,w of order four. If all three U_i are singletons, then |W|=4. Each w\in W sees at least two of the three singleton vertices. Choose one pair of such neighbors for each w. There are only three pairs, so two vertices w,w' choose the same pair \{u,v\}, again giving w,u,w',v,w. This rules out k=3.

The case k=4 with a clique of order four. Suppose first that Q=\{q_1,q_2,q_3,q_4\} is a clique. A path between distinct q_i,q_j with one, two, or three internal vertices outside Q can be completed to a C_5 by a path in Q of length three, two, or one, respectively. More explicitly, with q_h,q_\ell the other clique vertices, the prohibited configurations yield

In every row the exterior vertices are distinct and lie outside Q, so the displayed cycle has exactly five vertices.

The sets U_i are nonempty. Their closed neighborhoods in F are pairwise disjoint: an intersection of N_F[U_i] and N_F[U_j] would give vertices u\in U_i, v\in U_j at distance at most two in F, with u=v allowed. A shortest such path, joined to q_i and q_j, is one of the three prohibited configurations. In particular, every vertex u\in U_i has exactly one neighbor in Q, so it has at least three neighbors in F. It follows that

But |V(F)|=4a-3\le13, a contradiction. We may therefore assume that \omega(G)=3.

Triangles with disjoint exterior neighbor sets. For any triangle Q=\{q_1,q_2,q_3\}, every U_i has size at least two. A path between distinct triangle vertices with two or three internal vertices outside Q gives a C_5. In particular, if distinct u\in U_i, v\in U_j are adjacent, or are joined by a two-edge path u,z,v in F, the respective cycles are

where h is the remaining triangle index.

Suppose for the moment that U_1,U_2,U_3 are disjoint. By (4.1), their closed neighborhoods in F are also pairwise disjoint. A maximum independent subset J of U_i has exactly one neighbor in Q, namely q_i. Thus the assumed expansion bound gives

Here |V(F)|=4a-2\le14. If any U_i had independence number at least two, the three disjoint neighborhoods would together have at least 8+4+4=16 vertices. Hence every U_i is a clique. Its size is exactly two, because it has size at least two and adjoining q_i cannot produce a K_4.

If the exterior neighbor sets were disjoint for every triangle, write U_i=\{u_i,v_i\} and apply that assertion to the triangle T_i=\{q_i,u_i,v_i\}. Each of u_i,v_i has at least two neighbors outside T_i, and the two sets of such neighbors are disjoint. All of these vertices lie in F-U_i: the original disjointness prevents u_i or v_i from seeing a vertex of Q\setminus\{q_i\}. Consequently |N_F[U_i]|\ge2+2+2=6 for every i. The three original closed neighborhoods are disjoint, so this would require at least 18 vertices in F, again impossible. Some triangle therefore has overlapping exterior neighbor sets.

The necessary structure at an overlapping triangle. Take a triangle for which I=U_1\cap U_2\ne\varnothing. No other pair of exterior sets overlaps. Indeed, a vertex in all three sets would form a K_4 with Q. If x\in U_1\cap U_2 and y\in U_1\cap U_3 are distinct, then

is a C_5; if instead y\in U_2\cap U_3, use q_1,x,q_2,y,q_3,q_1. Also I is independent, since adjacent vertices x,y\in I would give the K_4 on q_1,q_2,x,y.

The four sets

have pairwise disjoint closed neighborhoods in F. To check this even for pairs involving I, choose distinct triangle neighbors for vertices in the six possible pairs of classes as follows:

If two vertices from the indicated classes were adjacent or shared a neighbor in F, the corresponding distinct triangle neighbors would close one of the cycles in (4.1). Since the classes themselves are disjoint, their closed neighborhoods are disjoint as claimed.

Write r=|I|. The set I is independent and its only neighbors in Q are q_1,q_2. Hence

Each nonempty one of A,B,D has exactly one triangle neighbor, so the argument of (4.2) bounds the size of its closed neighborhood below by four times its independence number. These bounds may be added because the four closed neighborhoods are disjoint.

If r=1, then both A and B are nonempty, since |U_1|,|U_2|\ge2, and D is nonempty as well. The four neighborhoods would have total size at least 3+4+4+4=15>14. If r\ge3, the neighborhoods of I and D alone would have total size at least 11+4=15>14. Thus r=2. In this case the neighborhoods of I and D already contribute at least 7+4=11 vertices; a nonempty A or B would increase the bound to 15. Therefore

Moreover, \alpha(D)\ge2 would give 7+8=15 vertices, so D is a clique. Its size is exactly two, by the degree bound and the absence of a K_4.

This argument proves a necessary statement for every triangle with overlapping exterior neighbor sets: exactly one pair overlaps, both sets in that pair equal an independent set of size two, and the third exterior neighbor set is a clique of size two. No condition on the exterior sets of other triangles was used in proving this statement.

The final contradiction. Write I=\{w,z\} and consider the triangle T=\{q_1,q_2,w\}. By (4.4), the exterior neighbor sets of its first two vertices are both

The necessary statement just proved therefore applies to T. Its third vertex w has exactly two neighbors outside T. Neither q_3 nor z is adjacent to w: adjacency to q_3 would give a K_4 with the original triangle, and I is independent. Thus the neighbors of w outside T are precisely its neighbors in the original graph F, and d_F(w)=2. The same reasoning applies to z. Consequently,

whereas (4.3) gives |N_F[I]|\ge7. This contradiction completes the case k=4 and the proof.□

Proof. A 2-connected graph has minimum degree at least two and therefore contains a cycle: all neighbors of an endpoint of a longest path lie on that path, and two such neighbors give a cycle. Choose a cycle C of maximum order, orient it, and write a^+ for the successor of a\in V(C).

Suppose that a component D of H-V(C) exists. Its set of neighbors on C contains at least two vertices. Indeed, it is nonempty by connectedness, and a unique such vertex would be a cutvertex of H. If a\in V(C) has a neighbor in D, then a^+ has none. Otherwise a path from a to a^+ with nonempty interior in the connected graph D could replace the edge aa^+, giving a longer cycle. This path exists even if a and a^+ have the same neighbor in D.

Choose distinct vertices a,b\in V(C) with neighbors in D, and a path P from a to b with nonempty interior in D. The vertices a^+,b^+ are distinct, neither equals a or b, and both have no neighbor in D. If a^+b^+ were an edge, we could traverse P from a to b, follow C backwards from b to a^+, use a^+b^+, and follow C forwards from b^+ to a. Deleting aa^+ and bb^+ from C leaves exactly the two cycle segments used here. Hence this would be a cycle containing every vertex of C and at least one additional vertex, a contradiction. Thus a^+ and b^+ are nonadjacent. Together with any vertex of D, they form an independent triple, also a contradiction. Therefore C is spanning.□

Proof. Label the vertices around a Hamiltonian cycle by 0,1,\ldots,r-1, with indices interpreted modulo r. If some edge joins i to i+2, it bypasses the vertex i+1 and gives the required cycle. Suppose there is no such edge. In each triple i,i+2,i+4, the pairs i(i+2) and (i+2)(i+4) are nonedges. Since the triple is not independent, i(i+4) is an edge. All cyclic step-four edges are therefore present.

Consider the cyclic sequence

Before closing, its three blocks partition the vertices 1,\ldots,r-1. Consecutive vertices within a block are adjacent on the original cycle. The three edges joining the blocks and closing the sequence are

their cyclic differences are 4,-4,4, respectively. Thus (5.1) is a cycle of order r-1. When r=7, the first block is the singleton 1, and the sequence is explicitly 1,5,6,2,3,4,1, so the same construction applies.□

Proof. Suppose that H=G[Y] has \alpha(H)\le2 and order n>\max\{k,2t\}. If H is disconnected, it has exactly two components, each a clique. Indeed, three components give an independent triple, as does a nonadjacent pair in one component together with a vertex of another. The two cliques have at most t vertices each, contrary to n>2t.

If H has a cutvertex v, the same argument shows that H-v has exactly two components A,B, both cliques of order at most t. The inequalities

force |A|=|B|=t. The vertex v must be adjacent to all of one component: a nonneighbor in each would form an independent triple with v. That component together with v is a clique of order t+1, again a contradiction.

Consequently H is 2-connected and has a Hamiltonian cycle by Lemma 5.1. Its order is n\ge k+1. If a current cycle has order r>k+1, the graph induced by its vertices is Hamiltonian, has independence number at most two, and satisfies r\ge k+2\ge7. Lemma 5.2 therefore produces a cycle of order r-1. Repeated shortening reaches exactly k+1, contradicting the hypothesis on G.□

Proof. Suppose such a system exists. The integer

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

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 6.1 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 (6.3).□

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 6.4. 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. At each target with an incoming path, retain its segment from the representative to the target. At a chain start the corresponding segment consists only of the target. Concatenate the reverse of the segment at q, the given outside path, and the segment at q'. Figure 2 illustrates the construction with two incoming paths. The two retained segments have disjoint interiors, and the outside path has its interior in F=G-S, so the resulting path is simple. In particular, a retained segment contains no clique vertex except its own target. This remains true when the two targets are consecutive on one chain.

After deleting the incoming paths, each target has degree at most one in the represented forest, and the targets lie in different components. If they belonged to different chains, this is immediate. If they belonged to the same chain, deleting the incoming edge at the later target separates them. The new edge between the targets thus creates neither a cycle nor a vertex of degree greater than two. It gives a valid linear forest.

If the deleted paths have total amount A, their retained segments contribute exactly A interior vertices to the new path. Its amount is therefore A+d, while the unchanged paths contribute L-A. The total is L+d, and the number of paths is e-r+1.□

Proof. The first type of path would give a system of amount L+1 by Lemma 7.1. For the second type, replace the step between the consecutive vertices by the proposed two-edge path. This keeps the represented forest and every old interior vertex, again increasing the amount to L+1.

Since L<h, either L+1<h, contrary to maximality of L, or L+1=h. In the latter case the new system has at most t incident clique vertices, and hence lies in the forbidden interval of Lemma 6.1.□

Proof. Every vertex of B_1(x;S) misses R\setminus\{x\}: an adjacency to another representative would give an outside path with one or two internal vertices.

Suppose first that B_2(x;S) were a clique. It contains B_1(x;S), whose order is at least k-|S|+t\ge t by (7.1). Since the maximum clique size is t, this forces

Each vertex z of this ball has at most t-1 neighbors in F, because all those neighbors lie in B_2(x;S). It also has at most k-t+1 neighbors in S, since it misses the other representatives. As \deg_G(z)\ge k, both bounds are attained. In particular every such z is adjacent to x. The ball together with x is then a clique of order t+1, a contradiction. Thus B_2(x;S) is not a clique and has an independent pair.

Now suppose that B_1(x;S) contains an independent pair I. Its closed neighborhood in F lies in B_2(x;S), and its neighborhood in S avoids R\setminus\{x\}. The expansion bound of Lemma 2.2 gives

When t<k, this is greater than \max(k,2t), so Lemma 5.3 gives an independent triple.□

Proof. Fix an orientation and suppose that no such path exists. Lemma 6.4 makes the t balls B_2(x;S), x\in R, pairwise disjoint and anticomplete. Each has an independent pair by Lemma 7.3, so together they give an independent set of order at least 2t. If 2t>k, this contradicts \alpha(G)\le k; this also settles the case t=k without using the independent-triple conclusion.

We may therefore assume 2t\le k. The bound \lfloor k/2\rfloor\le t from Theorem 3.1 now gives

In particular t<k, and it suffices to find two representatives whose first balls are not cliques. Lemma 7.3 would then give a combined independent set of order at least 2t+2>k.

If |S|<k, equation (7.1) gives |B_1(x;S)|>t at every representative, so any two suffice. It remains to consider |S|=k. In this case L=k-t>0, and hence e\ge 1.

Suppose first that e\ge 2. At least two representatives are interior vertices of paths of \mathcal P. For each such representative x, let y be the next vertex toward its target. This vertex is not in R: it is either a later interior vertex of the same path, or, when the amount is one, the target itself, which is not a chain start. By the consecutive-vertex assertion of Lemma 7.2, every outside neighbor of x misses y. The improved degree count following (7.1) yields

Thus the two chosen first balls are not cliques.

Finally suppose that e=1. The represented forest has one nonsingleton chain, consisting of a single edge, and t-2\ge 7 singleton chains. Let x be the representative of any singleton chain. Reverse the nonsingleton chain, leaving every other orientation fixed, and let y be its new starting clique vertex. The vertex y was not in the original representative set R, whereas x is a representative in both orientations. Lemma 7.2, applied to the reversed orientation, shows that every outside neighbor of x misses y. Consequently |B_1(x;S)|\ge t+1 once again. Choosing two singleton representatives gives the two required noncliques and the final contradiction. The reversed orientation was used only for the unconditional one-vertex exclusion; the assumed absence of paths with up to six internal vertices concerned the original orientation alone.□

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

because h+j\le L+d\le h+5. Lemma 6.1 gives

Since w\le t, this also excludes j=0. Thus

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

Together with (8.1), this implies

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

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 7.1 constructs a valid system of amount L+d, consisting of unchanged old paths and one new path. Lemma 8.1 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 8.1 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 6.1 gives

In particular, v\ge t-d. Since v\le2e and every old amount is at least d, we obtain

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

For d=3, dropping the ceiling in (8.3) 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

Thus v=2e=t-3, so no two old edges share a clique vertex. Equation (8.2) 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,

so L=10, k=19, and both amounts are five. Again (8.2) 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

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 2 has three or four edges, and that in Alternative 3 has two. In Alternative 1, if there were only one nonsingleton chain, then

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 7.2, every vertex of B_0(x;S) is nonadjacent to the other t-1 original representatives and to this additional clique vertex.

Lemma 8.2 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

Since t is the maximum clique size, this ball contains an independent pair I. The expansion inequality (2.2) and the containment N_G[I]\subseteq S\cup B_2(x;S) give

If k\ge2t, this exceeds \max(k,2t), so Lemma 5.3 supplies an independent triple.□

Proof. By Lemma 7.4, some pair of representatives admits an outside path with parameter between one and six. We may therefore apply Lemma 8.2. 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.

Alternative 1: at least one missing vertex. Put c=t-v, so 0\le c\le2, and first suppose c\ge1. Fix an orientation and choose the v=t-c representatives whose targets are incident to old paths. No pair of these targets covers the missing vertices. The endpoint restriction in Lemma 8.2 therefore forbids every outside parameter 1,\ldots,6 between any two chosen representatives. Their radius-two balls are pairwise disjoint and anticomplete by Lemma 6.4.

We claim that each of these balls contains an independent triple, even when k<2t. First,

For a chosen base x, Lemma 8.3 gives an independent pair I\subseteq B_1(x;S). There are at least two other chosen representatives, since v\ge t-2\ge7. For either such representative y, the prohibition of parameters one and two means that y has no neighbor in B_1(x;S), by Lemma 6.4. Thus at least two vertices of S are absent from N_G[I]. Since |S|=k, expansion gives

This exceeds both k and 2t, so Lemma 5.3 proves the claim. The separated balls now give an independent set of size at least

a contradiction.

Alternative 1: no missing vertex. Now c=0. The bounds

give e=\lceil t/2\rceil and k=t+L\ge2t. Lemma 8.3 therefore gives an independent triple in the radius-two ball of any representative. We select at least t-1 interior vertices as follows.

If t is even, then e=t/2 and v=2e, so the represented forest is a matching. Every amount is at least two, and L\le2e+1, so at most one amount exceeds two; if it does, it is three. Choose both interior vertices on each amount-two path, and one first interior vertex on the possible amount-three path. This chooses t or t-1 vertices.

If t is odd, then 2e=t+1, so L=t+1 and every amount is two. The forest has v-e=e-1 nonsingleton chains and e edges. Exactly one chain therefore has two edges, and all the others have one. Choose the two interior representatives of the two-edge chain in one fixed orientation. On each single-edge chain choose both interior vertices. This chooses

vertices.

Every chosen vertex is an interior representative in some orientation. Two chosen vertices on different chains can be representatives simultaneously, because the chains can be oriented independently. The two chosen vertices in the two-edge chain are simultaneous representatives by their definition. For any of these pairs, an outside path with parameter 1\le d\le6 would give, by Lemma 7.1, a new system of amount L+d that removes an old path. Lemma 8.1 rules this out.

The only pairs not yet covered are the two interior vertices a,b of a single amount-two path u,a,b,v. If an outside a-to-b path with parameter 1\le d\le6 existed, replace the step ab by it. The resulting u-to-v path has amount 2+d. Replacing the old path produces a valid system of amount L+d, consisting of e-1 unchanged paths and one new path. This again contradicts Lemma 8.1, which requires all old paths to remain.

Thus every pair of chosen bases forbids parameters 1,\ldots,6. Their radius-two balls are separated and give an independent set of size at least

another contradiction.

Alternative 2. Here e=(t-3)/2, every amount is at least three, and

since t\in\{9,11\}. In a fixed orientation, choose the representatives of all t-3 incident targets and one missing target. No pair has two missing targets, so the endpoint restriction forbids every parameter 1,\ldots,6 between chosen representatives. Their t-2 radius-two balls are separated and each contains an independent triple. They give

which is impossible.

Alternative 3. Here t=9 and k=19. Fix an orientation. At the four representatives with incident targets take radius-two balls, and at the five representatives with missing targets take radius-one balls. Among parameters 1,\ldots,6, the only potentially permitted parameter between representatives is five, and that requires two missing targets. Consequently, incident–incident pairs forbid parameters 1,\ldots,6, incident–missing pairs forbid parameters 1,\ldots,5, and missing–missing pairs forbid parameters 1,\ldots,4. These are exactly the prohibitions required by Lemma 6.4 for radius pairs (2,2), (2,1), and (1,1), respectively. All nine balls are therefore pairwise disjoint and anticomplete. Lemma 8.3, using 19\ge2\cdot9, supplies independent sets of total size

This final contradiction excludes every alternative and proves the proposition.□

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

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

The lower bound in (9.7) 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

contrary to Lemma 6.1. 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

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 6.4. 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

The balls are nested, so (9.9) 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 5.3 supplies an independent triple. These are precisely the additional bounds in (9.10), with the stated strict inequalities.

It remains to justify (9.11). If B_r(i;X) were a clique C, nesting and b_{r-1}=b_r=t would force

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

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 6.4. 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 (9.12) 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 9.6: restricting the allowed outside vertices cannot create a previously forbidden path. The additional required-path constraints are valid by Lemma 9.5. 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 9.4, and the constraints added in Step 2 are valid by Lemma 9.5. Inductively assume the current matrix contains valid prohibitions. Each new entry collected in Step 3 follows from that same matrix by Lemma 9.9. 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 9.8 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 9.1. Suppose such a graph exists and choose an optimal path system on a maximum clique. Lemma 9.2 places its pattern in the enumerated list. Lemma 9.3 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 5.3, and optimality gives Lemma 9.4. Proposition 9.10 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.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 2.2. Theorem 3.1 gives \max\{3,\lfloor k/2\rfloor\}\le t=\omega(G)\le k. Proposition 4.1 rules out k=3,4. For k\ge5, Proposition 8.4 rules out t\ge9. The remaining values satisfy (9.1), so Proposition 9.1 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.□