---

Claim. For every $n\ge3$, every graph on $2n+1$ vertices with $\binom{2n+1}2-\binom n2-1$ edges is the union of a bipartite graph and a graph of maximum degree below $n$. Pikhurko (p. 405) states it equivalently: $P_{n+1,n}$ has the fewest edges among the graphs of order $2n+1$ that arrow $(K_{1,n},\mathcal C_{\mathrm{odd}})$. [Er93] (p. 345) records that Erdős first reported Faudree's simple proof for $2n+1$ vertices in his paper [50], and it withdraws the induction claimed there for the general case. That paper is 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, which Pikhurko cites as [3] and the site lists under [Er81e]; it is the earliest record of the result, and the page name carries its year with a placeholder month and day.

Covers. The statement of Problem 613 restricted to graphs on $2n+1$ vertices. Not covered: graphs on $2n+2$ or $2n+3$ vertices, which [Er93] says Faudree's proof then reached and Pikhurko calls open at $2n+2$; and the general statement, which Pikhurko's constructions on $3n+1$ vertices disprove for $n\ge5$ (Pikhurko 2001).

Depends on. Nothing in this wiki.

Standing. Claimed. The site credits Faudree and calls his proof apparently unpublished, referring to [Er93]. Pikhurko (p. 405) cites Erdős, Reid, Schelp and Staton, Discrete Math. 158 (1996), no. 1--3, 283--286, linked above, for a proof; the authors listed are that paper's, and the result itself is credited to Faudree. The two accounts of publication differ, and the statement here follows Pikhurko and [Er93], so no evidence kind is listed. The site's label DISPROVED (LEAN) credits Pikhurko's disproof, so its credit to Faudree is not acceptance of this case.