In the 1960s, Erd\H{o}s and Gallai conjectured that the edges of every $n$-vertex graph can be decomposed into $O(n)$ cycles and edges. We prove this conjecture. Equivalently, every Eulerian graph on $n$ vertices can be decomposed into $O(n)$ cycles, which confirms Haj\'os'conjecture up to a constant factor.
Erd\H{o}s and S\'os conjectured that every $n$-vertex $3$-uniform hypergraph whose link graphs are all bipartite has at most $(1/4+o(1))\binom n3$ edges. We disprove this conjecture by constructing counterexamples with edge density at least $0.250000356>1/4$ for all sufficiently large $n$.
We present an exposition of a proof, discovered by GPT-6 Astra, of the Erd\H{o}s--S\'os Conjecture, which states that every graph with average degree greater than $t-2$ contains every tree on $t\geq 2$ vertices.
The Erd\H os--S\'os conjecture states that every $n$-vertex graph with more than $(k-2)n/2$ edges contains every $k$-vertex tree. We prove that for every $\gamma$ there is an $n_0$ such that for all $n\ge n_0$ and $k \ge \gamma n$ the conjecture holds. As a corollary of our result, we obtain a solution of a 51-year-old...
We prove the Erd\H{o}s--Chv\'atal simplex conjecture across its entire parameter range. If $2\le d<k$ and $(d+1)k\le dv$, then every $d$-simplex-free family of $k$-subsets of $[v]$ has at most $\binom{v-1}{k-1}$ members, with equality only for a full star.
It is shown that every Eulerian digraph on $n$ vertices with more than $(t-1)n$ arcs contains every oriented tree with $t$ edges. The digraphs have no loops or repeated arcs, but opposite arcs are permitted. The bound is sharp for each fixed oriented tree, as witnessed by disjoint unions of complete bidirected graphs....
Let $G$ be a connected graph of order $n$. Gallai conjectured that $G$ can be decomposed into $\frac{n+1}{2}$ paths. This is known as Gallai’s conjecture of path decomposition. In this paper, we focus on path decomposition of product graphs. It is proved that $G□H$ can be decomposed into $\frac{n(G□H)}{2}$ paths if $G$...
Tong-Shuo Zhang, Yang Zhang, Chui-Xiang Zhou· Annals of Applied Mathematic...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
