Problem 613

Let $n\geq 3$ and $G$ be a graph with $\binom{2n+1}{2}-\binom{n}{2}-1$ edges. Must $G$ be the union of a bipartite graph and a graph with maximum degree less than $n$ ?

Source: erdosproblems.com/613

Graph theory
Ramsey theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

The site labels the problem DISPROVED (LEAN). Theorem 1 of [Pi01], Combinatorica 21 (2001), 403--412 (refereed), gives $\hat r(K_{1,n},K_3)<n^2+\sqrt2\,n^{3/2}+n$ for $n\ge1$ by an explicit construction, and the paper notes (p. 405) that this beats $\binom{2n+1}2-\binom n2$ for all $n\ge6$ , while for $n=5$ its construction with the representation $5=2+3$ has $44$ edges against the conjectured $45$ . Since a graph arrowing $(K_{1,n},K_3)$ arrows $(K_{1,n},\mathcal C_{\mathrm{odd}})$ , the statement fails for every $n\ge5$ , and the site's commentary likewise records the failure at $n=5$ . The cases $n=3$ and $n=4$ (conjectured values $18$ and $30$ ) are not covered by the disproof and are not decided by any source cited here; the universal statement is false regardless. Theorem 1(2) of the same paper, $\hat r(K_{1,n},\mathcal C_{\mathrm{odd}})>n^2+0.577\,n^{3/2}$ for large $n$ , shows that the splitting does hold for graphs with at most that many edges. Faudree's special case, graphs on $2n+1$ vertices, is a pending partial claim on its claim page (Faudree, 1981). The claim page Pikhurko 2001 (the refereed disproof, accepted) records the result with its postings, its acceptance evidence and, as a formalization link, the third-party Lean proof of the $n=5$ instance; the frontmatter standing derives from that page.

Pi01: Pikhurko, O., Size Ramsey numbers of stars versus 3-chromatic graphs. Combinatorica 21 (2001), no. 3, 403--412, doi:10.1007/s004930100004 (received 28 May 1999). The conjectures, pp. 403--404; Theorem 1, p. 404; the $n=5$ remark and the remarks on Faudree's result, p. 405. Library home: Pikhurko 2001.
Er81e: The site's source key; the site's page prints no reference text for this key and this key is not in the site's reference table. [Pi01] cites for Erdős's conjecture P. Erdős, Problems and results in graph theory, in: The Theory and Applications of Graphs (G. Chartrand, ed.), Wiley, New York, 1981, 331--341 (its reference [3]).
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley (1991), 397--406.
Er93: Erdős, P., Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; the site cites p. 345. Chapter V, problem 9, printed p. 345: the splitting conjecture restated from Erdős's paper [50], with Faudree's proof for $2n+1$ , $2n+2$ and $2n+3$ vertices and the general case "still seems to be open". Library home: Erdős 1993.
Er99: Erdős, P., A selection of problems and results in combinatorics. Combin. Probab. Comput. 8 (1999), 1--6. [Pi01] cites it as its reference [4].
ERSS96: Erdős, P., Reid, T. J., Schelp, R. and Staton, W., Sizes of graphs with induced subgraphs of large maximum degree. Discrete Math. 158 (1996), 283--286. [Pi01] (p. 405) cites it for a proof of Faudree's result on graphs of order $2n+1$ .
MOS16: Miralaei, M., Omidi, G. R. and Shahsiah, M., Size Ramsey numbers of stars versus cliques. arXiv:1601.06599 (2016). Context on the clique generalization (abstract only).

Problem 613

Status

Proof claims

Discussion