Erdős Problem #1091

Erdős Problem 1091: a bounded number of cycle diagonals

1. The two questions

The first question asks whether every $K_4$-free graph with chromatic number four contains an odd cycle with two diagonals. This is Voss's known affirmative theorem; its proof is not reconstructed here. The second asks whether the guaranteed number of diagonals tends to infinity when every subgraph on at most $r$ vertices is three-colourable. We give a full negative answer to this second question. For every $m\ge1$ we construct a $K_4$-free graph $G_m$ on $20m+31$ vertices with chromatic number four, all proper subgraphs three-colourable, and at most ten diagonals in every cycle. This reconstructs Section 4 of Alexeev--Putterman--Sawhney--Sellke--Valiant, Short proofs in combinatorics, probability and number theory II, https://arxiv.org/abs/2604.06609. The paper attributes the construction to an internal OpenAI model and the stronger degeneracy verification to the human authors. No novelty is claimed.

2. The graph

Take disjoint pentagons $S_0,\ldots,S_m$, each with cyclic labels $a,b,c,d,e$. Join $S_i[c]$ to $S_{i+1}[a]$ for $0\le i<m$. Attach a new leaf pentagon by a single edge at each of the following positions: \[ S_0:\ a,b,d,e;\qquad S_i:\ b,d,e\ (1\le i<m);\qquad S_m:\ b,c,d,e. \] For each attached pentagon designate its endpoint of the attaching edge as its attachment vertex. Add one extra vertex $v$, adjacent to the other four vertices of every leaf pentagon and to no other vertices. There are $m+1$ spine pentagons and $3m+5$ leaves, hence $20m+31$ vertices in total. Every vertex except $v$ has degree exactly three. The graph $G_m-v$ is connected and consists of pentagons joined according to a tree by bridge edges. There is no triangle in $G_m-v$, since every cycle there lies in one pentagon. Consequently a $K_4$ cannot avoid $v$, and cannot contain $v$ either, since its other three vertices would form a triangle in $G_m-v$.

3. Four colours are necessary

Suppose a three-colouring exists and write $\alpha$ for the colour of $v$. The four nonattachment vertices of any leaf form a path on four vertices and cannot use $\alpha$. They alternate between the other two colours, so the path's endpoints have different colours. Its attachment vertex, adjacent to both endpoints, must therefore have colour $\alpha$. Every spine vertex with a leaf attached consequently avoids $\alpha$. In a pentagon, if $a,b,d,e$ avoid $\alpha$, they form the four-vertex path $b,a,e,d$. Its endpoints $b,d$ have different colours, forcing $c$ to have colour $\alpha$. Applying this to $S_0$ gives $S_0[c]=\alpha$, whence $S_1[a]\ne\alpha$. Inductively, the three leaf attachments on each internal spine pentagon and the preceding spine edge force \[ S_i[c]=\alpha\quad(0\le i<m),\qquad S_m[a]\ne\alpha. \] But the four vertices $b,c,d,e$ of $S_m$ all avoid $\alpha$ and form a four-vertex path. Its endpoints have different colours, forcing $S_m[a]=\alpha$, a contradiction.

4. Every proper subgraph is two-degenerate

We prove that no nonempty proper subgraph $H$ has minimum degree at least three. If it did, it would contain a vertex other than $v$. Since every such vertex has degree exactly three in $G_m$, all its neighbours and incident edges would belong to $H$. Connectivity of $G_m-v$ propagates this conclusion to every vertex of $G_m-v$. The neighbours of $v$ then force $v$ and every edge incident to it into $H$ as well. Thus $H=G_m$, a contradiction. Every nonempty subgraph of a proper $H$ is again proper, so successive deletion of a vertex of degree at most two gives a two-degeneracy ordering. Greedy colouring in reverse order uses three colours. Finally $G_m-v$ is three-colourable, and assigning a fourth colour to $v$ shows $\chi(G_m)=4$.

5. Counting every possible diagonal

A cycle avoiding $v$ lies inside one pentagon and has no diagonals. For a cycle $C$ containing $v$, deleting $v$ leaves a simple path $P$ in $G_m-v$ whose endpoints are nonattachment vertices of leaves. A bridge cannot be traversed twice by a simple path. Thus the visited pentagon blocks form a path in the block tree. There is one exceptional case worth treating separately: if the two endpoints lie in the same leaf, $P$ stays in that leaf. The induced graph on that leaf and $v$ has only nine edges, so such a cycle has at most $9-3=6$ diagonals. Otherwise the path has two distinct leaf blocks at its ends and a segment of spine blocks between them. In each end leaf, $P$ is a rim path from the attachment vertex to one vertex adjacent to $v$. At most three internal vertices of this path contribute diagonals to $v$. At most one further diagonal is possible within the pentagon: the unused rim edge joining the path's endpoints. Thus each leaf contributes at most four. In a spine block strictly between the two end spine blocks, the rim path runs from $a$ to $c$. These vertices are not adjacent in the pentagon, so there is no internal diagonal. Each end spine block contributes at most one unused endpoint edge; if the two ends coincide there is just one such block, and the bound of two remains valid. There are no diagonals between distinct blocks: their only connecting edges are bridges, and any such edge whose endpoints lie on $P$ must itself belong to $P$. Vertex $v$ has no spine neighbours. All diagonals have therefore been counted, giving \[ \#\{\text{diagonals of }C\}\le4+4+1+1=10. \]

6. Consequence and remaining scope

For any $r$, choose $m$ with $20m+31>r$. All subgraphs on at most $r$ vertices are proper and three-colourable, whereas every cycle has at most ten diagonals. A function tending to infinity cannot be guaranteed. The quantitative second question is completely disproved, including every-subgraph criticality and the same-leaf cycle case. The proof of the separate two-diagonal theorem of Voss remains an external known result, so this attempt is not a complete reconstruction of both questions. The first-part proof obligation is unresolved in this attempt, although the theorem itself is known. Source statement: https://www.erdosproblems.com/1091.

Completion rate estimate: 85%.

FORMAL RESTATEMENT

All graphs are finite, simple, undirected. A diagonal of a cycle $C=v_0v_1\dots v_{\ell-1}v_0$ means a chord: an edge $v_iv_j$ with $|i-j|\not\equiv 1 \pmod \ell$.

Question $1$: If $G$ is $K_4$-free and $\chi(G)=4$, must $G$ contain an odd cycle with at least two diagonals?

Question $2$: Does there exist a function $f(r)\to\infty$ such that every graph $G$ with $\chi(G)=4$ and with the property that every subgraph on $\le r$ vertices has chromatic number $\le 3$ contains an odd cycle with at least $f(r)$ diagonals?

QUICK LITERATURE/CONTEXT CHECK

I will not use external results beyond what is explicitly stated in the problem text. The text states: the existence of an odd cycle with at least one diagonal is true (Larson), and the first question (two diagonals) was solved affirmatively by Voss. The pentagonal wheel shows that three diagonals are not guaranteed.

ATTACK PLAN

• Reduce to a minimal counterexample: take a $4$-critical subgraph (every proper subgraph is $3$-colorable). This forces strong structural properties (minimum degree $\ge 3$, 2-connectedness).
• Use coloring/Kempe-chain arguments on $3$-colorings of $G-e$ (for an edge $e$) to force the existence of specific alternating paths, hence many odd cycles.
• The missing step is to upgrade "many odd cycles" into one odd cycle that has two chords and to do so under the additional $K_4$-free constraint.

WORK

Lemma 1091.1 (Existence of a $4$-critical subgraph). If a graph $G$ satisfies $\chi(G)=4$, then $G$ has a subgraph $H\subseteq G$ such that $\chi(H)=4$ and every proper subgraph of $H$ has chromatic number at most $3$. Moreover, if $G$ is $K_4$-free, then $H$ is $K_4$-free.

Proof. Among all subgraphs of $G$ with chromatic number $4$, choose one $H$ with the minimum number of vertices; among those, choose one with the minimum number of edges. Then $\chi(H)=4$ by construction. If $H'$ is a proper subgraph of $H$, then either it has fewer vertices (if obtained by deleting a vertex) or the same vertices and fewer edges; in either case, by minimality of $H$, we must have $\chi(H')\le 3$. Thus $H$ is $4$-critical in the standard sense. If $G$ is $K_4$-free, then any subgraph of $G$ is also $K_4$-free, in particular $H$. $\square$

Lemma 1091.2 (Basic properties of $4$-critical graphs). Let $H$ be $4$-critical.

• (Minimum degree) Every vertex of $H$ has degree at least $3$.
• (2-connectedness) $H$ has no cut vertex (equivalently, $H$ is 2-connected).

Proof. Minimum degree. Suppose for contradiction that $H$ has a vertex $v$ with $\deg_H(v)\le 2$. By $4$-criticality, $H-v$ is $3$-colorable; fix a proper 3-coloring of $H-v$. The vertex $v$ has at most two neighbors, so among the three colors there is at least one color not used on its neighbors. Assign that color to $v$; this yields a proper 3-coloring of $H$, contradicting $\chi(H)=4$. Hence $\delta(H)\ge 3$.

2-connectedness. Suppose $H$ has a cut vertex $v$. Then $H-v$ has at least two connected components; let $H_1,H_2$ be the induced subgraphs on $v$ together with the vertex sets of two distinct components (so $H=H_1\cup H_2$ and $H_1\cap H_2=\{v\}$). By $4$-criticality, both $H_1$ and $H_2$ are proper subgraphs of $H$, hence each is 3-colorable. Take proper 3-colorings of $H_1$ and $H_2$; by permuting color names in one of them, we may assume $v$ receives the same color in both. Then combining the two colorings gives a proper 3-coloring of all of $H$, contradicting $\chi(H)=4$. Thus $H$ has no cut vertex. $\square$

Lemma 1091.3 (Kempe-chain forcing for a critical edge). Let $H$ be $4$-critical and let $uv\in E(H)$. Then in every proper 3-coloring of $H-uv$, the vertices $u$ and $v$ receive the same color. Moreover, fix such a 3-coloring with colors $\{1,2,3\}$ and suppose $u$ and $v$ have color $1$. Then:

• $u$ and $v$ lie in the same connected component of the subgraph induced by colors $\{1,2\}$ (a $1$--$2$ Kempe chain).
• $u$ and $v$ lie in the same connected component of the subgraph induced by colors $\{1,3\}$ (a $1$--$3$ Kempe chain).

In particular, $H$ contains two (not necessarily internally disjoint) $u$--$v$ paths of even length: one alternating colors $1,2$ and one alternating colors $1,3$. Consequently, the edge $uv$ lies on (at least) two odd cycles.

Proof. Because $H$ is $4$-critical, the proper subgraph $H-uv$ is 3-colorable. Let $\varphi$ be a proper 3-coloring of $H-uv$. If $\varphi(u)\neq\varphi(v)$, then $\varphi$ would also be a proper 3-coloring of $H$ (since adding the edge $uv$ would still connect differently colored vertices), contradicting $\chi(H)=4$. Thus necessarily $\varphi(u)=\varphi(v)$.

Now assume $\varphi(u)=\varphi(v)=1$. Consider the induced subgraph $H[\varphi^{-1}(\{1,2\})]$. If $u$ and $v$ lie in different connected components of this induced subgraph, then swapping colors $1$ and $2$ on the component containing $u$ produces another proper 3-coloring of $H-uv$ in which $u$ has color $2$ while $v$ remains color $1$. Then $u$ and $v$ have different colors, and the edge $uv$ can be added without creating a monochromatic edge, giving a proper 3-coloring of $H$, contradiction. Therefore $u$ and $v$ must lie in the same connected component of $H[\varphi^{-1}(\{1,2\})]$. The same argument with colors $1$ and $3$ shows $u$ and $v$ lie in the same component of $H[\varphi^{-1}(\{1,3\})]$.

Any path in the $\{1,2\}$-induced subgraph alternates colors and has even length when both endpoints have color $1$; similarly for the $\{1,3\}$-induced subgraph. Adding the edge $uv$ to either even-length path yields an odd cycle containing $uv$. $\square$

FAST REALITY CHECK (local computation). The pentagonal wheel $W_5$ (5-cycle plus a hub adjacent to all rim vertices) is $K_4$-free and has chromatic number $4$. A brute-force check on this 6-vertex graph found an odd 5-cycle with exactly two diagonals, e.g. cycle $(0,1,2,5,4)$ has chords $(0,5)$ and $(1,5)$.

VERIFICATION

• Lemmas 1091.1--1091.3 are standard critical-graph facts; I verified each step does not assume planarity or any forbidden subgraph beyond the stated hypotheses.
• Lemma 1091.3 uses only the Kempe-chain recoloring argument, which is valid for any proper coloring.
• None of these lemmas by itself forces two chords in a single odd cycle; they only force the existence of many odd cycles through a given edge.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Any $K_4$-free graph $G$ with $\chi(G)=4$ contains a $4$-critical $K_4$-free subgraph $H$ with $\delta(H)\ge 3$ and no cut vertex. For any edge $uv\in E(H)$, $uv$ lies on at least two odd cycles (Lemma 1091.3).

(ii) First gap (crisp). Starting from the forced existence of multiple odd cycles through edges in a $4$-critical $K_4$-free graph, prove that some odd cycle must contain two distinct chords (two diagonals).

(iii) Top 3 next moves.

• Strengthen Lemma 1091.3 to produce a "theta" subgraph with three internally disjoint $u$--$v$ paths, and analyze when such a theta forces an odd cycle with two chords.
• Exploit $K_4$-freeness: in the theta configuration, any additional edge between internal vertices of two paths creates either a chorded cycle or a $K_4$; use this to force many chords.
• For the more general local-to-global question, experiment computationally with known sparse 4-chromatic constructions (e.g. iterated Mycielski graphs) to measure the maximum number of chords forced in odd cycles as a function of local 3-colorability radius.

(iv) Minimal counterexample structure. A minimal counterexample to Question $1$ would be a $4$-critical, $K_4$-free graph $H$ such that every odd cycle of $H$ has at most one chord. Such an $H$ must be 2-connected with minimum degree at least 3 (Lemma 1091.2) and must have the strong Kempe-chain property for each edge (Lemma 1091.3).