Erdős Problem #916

Erdős Problem #916: a cycle with three unsubdivided spokes

Statement and plan

Does every finite simple graph with $n\geq3$ vertices and at least $2n-2$ edges contain a cycle and a vertex outside it adjacent to at least three vertices on it? Call this configuration a wheel in this attempt; the rim may be long, but its three spokes must be edges. We reconstruct Thomassen's stronger theorem: a wheel-free graph of order $n\geq3$ has at most $2n-3$ edges, and equality holds exactly for the graphs obtained by repeatedly gluing triangles and $K_{3,3}$'s along edges. Call these graphs cockades.

Elementary facts about cockades

Every cockade is 2-connected, has $2n-3$ edges, and is wheel-free. These statements hold for a triangle and $K_{3,3}$. For gluing along an edge $xy$, the counts satisfy $n=n_1+n_2-2$, $e=e_1+e_2-1=2n-3$. A centre outside $\{x,y\}$ has neighbours only on its own side. If a rim crosses the other side, replace its exterior $x$-to-$y$ portion by the edge $xy$, retaining all three neighbours. If the centre is $x$ or $y$, deleting it leaves a cutvertex between the sides, so a rim lies on one side. Thus a new wheel is impossible. The 2-connectivity follows directly by deleting any one vertex from the gluing.

We also need two augmentation facts.

Fact A. Adding to a cockade an exterior path between nonadjacent vertices creates a wheel. This is vacuous for a triangle. In $K_{3,3}$, the two nonadjacent endpoints are in the same part. If that part is $\{a,b,c\}$ and the exterior path joins $a,b$, choose two vertices $u,v$ of the other part. The rim consisting of the exterior path followed by $b,u,c,v,a$ has the remaining vertex of the other part as centre. For a gluing $G_1\cup G_2$ along $xy$, endpoints on one side are handled by induction. Otherwise write the endpoints as $a\in G_1-\{x,y\}$, $b\in G_2-\{x,y\}$. A path from $b$ to $x$ in $G_2-y$, together with the new exterior path, gives an exterior $a$-to-$x$ path for $G_1$. Thus if $ax$ is absent induction gives a wheel; similarly for $ay,bx,by$. If all four edges are present, the exterior path together with $a,y,b$ is a rim to which $x$ has the three neighbours $a,y,b$. This proves Fact A.

Fact B. Suppose $bc$ is an edge of a cockade and $a$ is adjacent to neither $b$ nor $c$. Delete $bc$, add a new vertex $z$, and add $za,zb,zc$. The result contains a wheel. The configuration of $a,b,c$ is impossible in either base graph. For a gluing along $xy$, use induction if all three vertices lie on one side. Otherwise $a$ lies strictly in $G_1$ and $bc$ is an edge of $G_2$ different from $xy$. Subdivide $bc$ by $z$ in $G_2$. This graph is 2-connected, so it has a $z$-to-$x$ path avoiding $y$. Prepending $az$ gives an exterior $a$-to-$x$ path for $G_1$. By Fact A we may assume $ax$ and, symmetrically, $ay$ are both present. In a 2-connected graph any two edges lie on a common cycle: subdivide the two edges and apply the two-vertex form of Menger's theorem. Choose such a cycle through $xy$ and $bc$ in $G_2$, then replace $bc$ by $b,z,c$. Its vertices include $x,y,z$, all adjacent to $a$, which is outside the cycle. This proves Fact B.

Induction and separators of size at most two

Induct on $n$ in the stronger assertion. If a wheel-free graph has more than $2n-3$ edges, retain exactly $2n-3$ of them, obtaining $G_0$. It suffices to show $G_0$ is a cockade: any omitted edge would join nonadjacent vertices of $G_0$, and Fact A would create a wheel.

Thus consider wheel-free $G_0$ with $e(G_0)=2n-3$. It is 2-connected. Otherwise split it into proper subgraphs meeting in at most one vertex. Each piece of order at least two has at most twice its order minus three edges by induction (also valid for order two), giving at most $2n-4$ edges in total. An isolated vertex instead leaves a smaller graph exceeding its allowed bound.

Every separating pair $x,y$ must be adjacent. Indeed, split $G_0=G_1\cup G_2$, with intersection $\{x,y\}$. If one side were a cockade and $xy$ absent, an exterior $x$-to-$y$ path in the other side would contradict Fact A. Thus each side has at most $2|G_i|-4$ edges by induction, giving at most $2n-4$ altogether. If a separating pair is adjacent, the usual count is \[ 2n-3=e(G_1)+e(G_2)-1 \leq2(|G_1|+|G_2|)-7=2n-3. \] Both sides attain equality, hence are cockades; their gluing is a cockade. It remains to treat the 3-connected case.

Preparations in the 3-connected case

A 3-connected wheel-free graph is triangle-free. If $a,b,c$ form a triangle, choose another neighbour $d$ of $a$. The 2-connected graph $G_0-a$ contains a cycle through $d$ and the edge $bc$, giving a wheel centred at $a$. Here the cycle-through-a-vertex-and-an-edge fact follows by subdividing that edge and using Menger's theorem.

For order at most six, triangle-freeness and minimum degree at least three force the order to be six and the graph to be $K_{3,3}$. Indeed, three neighbours of a vertex are independent and each needs two additional neighbours outside this neighbourhood and the vertex. At order six, $e=9$ forces all degrees to be three, and those two additional vertices must join all three neighbours. Hence assume $n\geq7$.

Deleting the vertices of any two-edge path $x,y,z$ leaves a connected graph. Otherwise split along $\{x,y,z\}$. The graph is triangle-free, so $xz$ is absent. Each side has an exterior $x$-to-$z$ path through the other side avoiding $y$, since 3-connectivity forces every component of the deletion to attach to all three separator vertices. Fact A excludes either side being a cockade. Induction therefore gives \[ e(G_0)\leq (2n_1-4)+(2n_2-4)-2=2n-4, \] because $n_1+n_2=n+3$. This is impossible.

Let $V_3$ be the vertices of degree three. The identity $e=2n-3$, together with minimum degree three and $n\geq7$, shows $V_3$ is nonempty and not all vertices. Moreover $G_0[V_3]$ is a forest. If it had a shortest cycle $C$ of length $s$, then $C$ would be chordless and each of its vertices would have exactly one neighbour outside $C$. Consequently \[ e(G_0-C)=2(n-s)-3. \] There are at least two vertices outside $C$. If there are exactly two, then $s=n-2\geq5$, and one outside vertex has at least three neighbours on $C$, a wheel. If there are at least three, induction makes $G_0-C$ a cockade. Its neighbours from $C$ include at least three distinct vertices by 3-connectivity, and two of them are nonadjacent by triangle-freeness. The corresponding arc through $C$ is an exterior path, contradicting Fact A.

Suppressing a degree-three vertex

A leaf or isolated vertex of the forest $G_0[V_3]$ gives a degree-three vertex $x_0$ with neighbours $x_1,x_2,x_3$, where $d(x_1),d(x_2)\geq4$. These neighbours are pairwise nonadjacent. Form \[ H=G_0-x_0+x_1x_2. \] It has $2|H|-3$ edges. If it were a cockade, Fact B, with $a=x_3,b=x_1,c=x_2$, would give a wheel in $G_0$. So induction gives a wheel in $H$.

The new edge $x_1x_2$ must be a spoke: if absent from that wheel, or on its rim, replacing it if needed by $x_1,x_0,x_2$ gives a wheel in $G_0$. Interchanging $x_1,x_2$ if necessary, its centre is $x_1$. Thus $G_0-\{x_0,x_1\}$ has a cycle $C$ containing $x_2$, with two distinct vertices $y_1,y_2$ adjacent to $x_1$.

We next obtain a cycle $C'$ in $G_0-\{x_0,x_1\}$ containing all four vertices $x_2,x_3,y_1,y_2$. There is nothing to do if $x_3\in C$. Otherwise 2-connectivity of $G_0-x_0$ gives two internally disjoint paths from $x_3$ to distinct vertices of $C\cup\{x_1\}$, with interiors outside that set. Call their ends $z_1,z_2$. Let $P_1$ be the $y_1$-to-$y_2$ arc of $C$ avoiding $x_2$.

If an end is $x_1$, combine the two paths with an arc of $C$ from the other end through $x_2$ to one of $y_1,y_2$, and the edge back to $x_1$. This is a cycle through $x_1,x_2,x_3$, giving a wheel centred at $x_0$.

If an end lies on $C-(\operatorname{int}P_1\cup\{x_2\})$, there is an arc from that end to $x_2$ containing both $y_1,y_2$. Combine it with the path from $x_3$ to that end and the edges $x_3x_0,x_0x_2$. The resulting rim contains $x_0,y_1,y_2$, giving a wheel centred at $x_1$.

If an end is $x_2$, the other end must now lie inside $P_1$. Use the two paths, the arc from that other end to $y_2$ inside $P_1$, the edges $y_2x_1,x_1y_1$, and the arc from $y_1$ to $x_2$ outside $P_1$. Again this is a cycle through $x_1,x_2,x_3$, impossible.

Thus both ends lie inside $P_1$. Replace the arc between them contained in $P_1$ by their two paths through $x_3$. This gives the claimed $C'$.

The final rerouting

Because $d(x_1)\geq4$, choose a neighbour $x_4\notin\{x_0,y_1,y_2\}$. It is neither $x_2$ nor $x_3$, by triangle-freeness. The earlier deletion result, applied to the path $y_1,x_1,y_2$, says $G_0-\{x_1,y_1,y_2\}$ is connected. Take a path from $x_4$ to its first vertex in $C'\cup\{x_0\}$. That first vertex cannot be $x_0$, since the remaining neighbours of $x_0$ are $x_2,x_3$, already on $C'$. Thus this path avoids $x_0$ and ends on $C'$ at a vertex different from $y_1,y_2$.

Together with $C'$, the edges $x_1y_1,x_1y_2,x_1x_4$, and that path, we have a subdivision of $K_4$ with branch vertex $x_1$ and the other three branch vertices on $C'$. Such a subdivision has a cycle through $x_1$ and any prescribed two vertices of its rim. Indeed, the three rim arcs between the spoke attachments include an arc whose interior contains neither prescribed vertex; omit that arc and use the two corresponding spokes. Apply this to $x_2,x_3$. The resulting cycle contains $x_1,x_2,x_3$, avoids $x_0$, and therefore gives a wheel centred at $x_0$. This contradiction completes the induction and proves the desired threshold.

Sharpness and attribution

The graph formed from $K_{2,n-2}$ by joining its two-vertex part has $2n-3$ edges and no wheel: each vertex in the other part has degree two, and deleting either possible high-degree centre leaves a star. Thus the threshold $2n-2$ is exact.

This is a reconstruction of Thomassen's proof and cockade characterization, not a novel theorem. Sources: https://www.erdosproblems.com/916; Thomassen, A minimal condition implying a special $K_4$-subdivision in a graph, Archiv der Mathematik 25 $1974$, 210--215, https://link.springer.com/content/pdf/10.1007/BF01238666.pdf. The standard external input is the vertex form of Menger's theorem for the elementary path and cycle facts. The induction, augmentation facts, separator counts and final rerouting are provided above. Attempt status: solved.

COMPLETION ESTIMATE

COMPLETION: 100%