gpt pro 5.2 attempt on Math-709

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.