0
$\begingroup$

I was curious if there was a reference which answers the question, What is the maximum number of edges in a graph $G$ with $n$ vertices which does not contain a $5$-cycle? $k$-cycle? The analogous question for $k=4$ is well known.

$\endgroup$
7
$\begingroup$

For cycles of odd length, the only extremal graphs for large $n$ are complete bipartite graphs with the sides as equal as possible. For smaller $n$ there can be other extremal graphs. The complete story was worked out fairly recently by Füredi and Gunderson.

Cycles of even length are much harder. Some references are given in this paper and more in this paper. See this paper too. Basically there are lots of partial results but the exact general solution is out of reach.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.