Erdős Problem #184

Erdős Problem 184: long-cycle deletion and the linear lower barrier

1. Statement and scope

Must the edges of every $n$-vertex graph be partitionable into $O(n)$ simple cycles and single edges? We give a complete elementary $O(n\log n)$ decomposition and an exact family needing $4(n-3)/3$ parts. The linear upper-bound conjecture remains unresolved. The current $O(n\log^*n)$ theorem recorded on the problem page is stronger than the upper bound reconstructed here; no new upper order is claimed.

2. Finding a cycle long enough for the current edge count

Let a graph on at most $n$ vertices have $e>n$ edges. It has a nonempty subgraph of minimum degree at least $e/n$. To see this, repeatedly delete a vertex of degree strictly below $e/n$, where this threshold refers to the original $e,n$. If all vertices were deleted, summing the degrees at their deletion times would count every edge exactly once and give a total strictly below $n(e/n)=e$, a contradiction.

In the remaining subgraph let $v_1,\ldots,v_s$ be a longest path and let its minimum degree be $\delta$. Every neighbour of $v_s$ lies on the path. If $v_i$ is its earliest neighbour, the $\delta$ distinct neighbours imply $i\le s-\delta$. Since $\delta\ge2$, the edge $v_sv_i$ and the path segment form a simple cycle of length \[ s-i+1\ge\delta+1>e/n.\tag{1} \] Thus whenever more than $n$ edges remain, there is a cycle longer than the current edge count divided by $n$.

3. A complete logarithmic decomposition

Repeatedly remove a cycle supplied by $1$, stopping once at most $n$ edges remain; use those remaining edges as singleton parts. All removed cycles and leftover edges are edge-disjoint and cover the graph.

Group the removals into phases in which the current edge count lies in \[ (2^j n,2^{j+1}n]\qquad(j\ge0). \] Every removal in such a phase deletes more than $2^j$ edges. If there are $r$ removals in that phase, the first $r-1$ leave the count above its lower endpoint, so \[ (r-1)2^j<2^{j+1}n-2^jn=2^jn. \] Hence $r\le n$. There are at most $1+\lceil\log_2 n\rceil$ phases, since the initial graph has at most $\binom n2$ edges. Including the at most $n$ single edges, the number of parts is at most \[ n\left(2+\lceil\log_2 n\rceil\right)\qquad(n\ge2).\tag{2} \] Empty and one-vertex graphs are immediate exceptions with zero parts.

4. Why a coefficient larger than one is necessary

Consider $K_{3,m}$, on $n=m+3$ vertices. Let a decomposition use $s$ single-edge parts and $c$ cycles. Each vertex of the size-$m$ class has odd degree three, whereas cycles use an even number of its incident edges. It must therefore meet at least one singleton edge. Each singleton meets just one vertex of this class, so $s\ge m$. Every simple cycle in $K_{3,m}$ has length at most six. Consequently \[ 6c\ge3m-s,\qquad c+s\ge\frac{3m-s}{6}+s\ge\frac{4m}{3}.\tag{3} \] If $3\mid m$, this bound is attained. Partition the large class into triples $\{b_1,b_2,b_3\}$; writing the small class as $\{a_1,a_2,a_3\}$, take the cycle $a_1b_1a_2b_2a_3b_3a_1$ for each triple. In its $K_{3,3}$ block the three unused edges form a matching and are taken singly. Each triple therefore costs four parts, for exactly $4m/3$ in total.

Thus the edge-disjoint version cannot always use merely $n-1$ parts. This does not contradict a conjecture allowing overlaps, which is a different covering problem.

5. Assessment

The logarithmic decomposition, the odd-degree obstruction and the exact examples at $3\mid m$ are proved. Removing the logarithmic overhead in the upper bound is the missing step. A maximal cycle packing leaving a forest does not by itself do that: the number of packed cycles also needs control. The earlier draft's obsolete best-bound attribution is not repeated; current context is taken from https://www.erdosproblems.com/184.

Completion rate estimate: 30%.

Erdős problem 184

1) FORMAL RESTATEMENT

Given a finite simple graph $G=(V,E)$ on $n=|V|$ vertices, an edge-decomposition into cycles and edges is a partition of $E$ into parts each of which is either: (a) the edge-set of a (simple) cycle, or (b) a single edge. Let $\phi(G)$ be the minimum number of parts in such a partition. Conjecture (Erdős--Gallai): $\phi(G)=O(n)$ for all $n$-vertex graphs. Equivalently: $\exists C$ such that $\phi(G)\le Cn$ for all graphs $G$.

2) QUICK LITERATURE/CONTEXT CHECK

Only what is stated in the problem text: currently best upper bound is $O(n\log n)$ (Conlon--Fox--Sudakov; and also independently by Thomassé). A lower bound example $K_{3,n-3}$ forces $\phi(G)\ge (1+c)n$.

3) ATTACK PLAN

Give: $1$ a clean cycle-decomposition for Eulerian graphs, $2$ a maximal-cycle-packing lemma leaving a forest, $3$ a full verification of the $K_{3,n-3}$ lower-bound mechanism.

4) WORK

Lemma 4.1 (Eulerian graphs decompose into edge-disjoint cycles).

If every vertex of $G$ has even degree, then $E(G)$ can be partitioned into edge-disjoint cycles. Proof. If $E(G)=\emptyset$ we are done. Otherwise pick a vertex $v$ in a nonempty component. Walk along unused edges greedily: from the current vertex, since degree is even, whenever you enter a vertex along an unused edge, there remains at least one unused edge to leave unless you have used up all incident edges. Because the graph is finite, the walk eventually repeats a vertex; the first repeated vertex closes a cycle using only unused edges. Remove those cycle-edges from $G$. Removing a cycle subtracts degree $2$ at each of its vertices, preserving even degrees. Iterate until no edges remain. The removed cycles are edge-disjoint by construction and cover $E(G)$. $\square$

Lemma 4.2 (Maximal edge-disjoint cycles leave a forest).

Let $\mathcal{C}$ be a maximal family of pairwise edge-disjoint cycles in $G$, and let $H$ be the graph obtained by deleting all edges in $\cup_{C\in\mathcal{C}}E(C)$. Then $H$ is acyclic (a forest), hence $|E(H)|\le n-1$. Proof. If $H$ contained a cycle $C'$, then $C'$ is edge-disjoint from every cycle in $\mathcal{C}$ (since its edges remain in $H$), contradicting maximality. So $H$ is cycle-free, i.e. a forest. Any forest on $n$ vertices has at most $n-1$ edges. $\square$

Lemma 4.3 ($K_{3,n-3}$ needs $\ge \frac43(n-3)$ parts).

Let $G=K_{3,n-3}$ with bipartition $(A,B)$, $|A|=3$, $|B|=n-3$. Then any decomposition of $E(G)$ into edge-disjoint cycles and single edges uses at least $\frac43(n-3)$ parts. Moreover, if $3\mid (n-3)$ this bound is attained. Proof. In a bipartite graph every cycle alternates between $A$ and $B$, so a simple cycle uses the same number of vertices from each side. Since $|A|=3$, any cycle uses at most $3$ vertices from $B$.

Fix any such decomposition. Let $t$ be the number of vertices in $B$ that lie on at least one cycle-part. Because $\deg_G(b)=3$ for $b\in B$ and a cycle uses exactly $2$ edges incident to each vertex it contains, a vertex $b\in B$ can be in at most one cycle-part (otherwise it would require at least $4$ distinct incident edges). Thus each of the $t$ vertices contributes exactly $2$ edges to cycle-parts; hence the total number of edges covered by cycle-parts equals $2t$ (each edge has a unique endpoint in $B$).

Total edges $|E(G)|=3(n-3)$. Therefore the number of single-edge parts is \[ 3(n-3)-2t. \] Let $c$ be the number of cycle-parts. Since each cycle uses at most $3$ vertices of $B$ and these are disjoint across cycles, $t\le 3c$, hence $c\ge t/3$. Total number of parts is \[ c+\left(3(n-3)-2t\right)\ \ge\ \frac{t}{3}+3(n-3)-2t\ =\ 3(n-3)-\frac53 t. \] Since $t\le n-3$, we obtain \[ \text{parts}\ \ge\ 3(n-3)-\frac53 (n-3)=\frac43(n-3). \]

For sharpness when $3\mid(n-3)$: partition $B$ into triples $\{b_1,b_2,b_3\}$ and for each triple use the $6$-cycle $a_1b_1a_2b_2a_3b_3a_1$, covering $2$ edges at each $b_i$. This gives $(n-3)/3$ cycles and leaves exactly one incident edge at each $b\in B$, i.e. $n-3$ single edges. Total parts $(n-3)/3+(n-3)=\frac43(n-3)$. $\square$

5) VERIFICATION

Lemma 4.3 crucially uses: (a) bipartite cycles alternate, (b) degree-$3$ vertex cannot lie in two edge-disjoint cycles, (c) each cycle uses at most $3$ vertices from $B$ because $|A|=3$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial results: Eulerian graphs admit a cycle partition (Lemma 4.1) and any maximal cycle packing leaves $\le n-1$ leftover edges (Lemma 4.2). Also $K_{3,n-3}$ forces $\phi(G)\ge \frac43(n-3)$ (Lemma 4.3), matching the stated "$(1+c)n$" barrier.

(ii) First gap: prove an absolute constant $C$ such that every $n$-vertex graph satisfies $\phi(G)\le Cn$.

(iii) Top 3 next moves: 1. Prove a linear-sized cycle-packing lemma capturing a constant fraction of remaining edges per round. 2. Develop a structural reduction to sparse graphs plus Eulerian remainder. 3. Explore extremal obstructions beyond $K_{3,n-3}$ (likely bipartite with small side).

(iv) Minimal counterexample structure: a family of graphs with $\phi(G)/n\to\infty$ would need to force that every cycle packing covers only $o(n)$ edges per cycle-part, suggesting bounded small-side bipartite structure and very limited long cycles.