Erdős 1016 & Graph Theory

Three results on the cycles of a graph. Each result has a guided tour with examples, and a paper with the complete proof.

  1. Erdős 1016

    A graph on n vertices with a cycle of every length has at least n+log2⁡n+log∗⁡n edges, with an error of a bounded number of edges. This many edges are also sufficient.

    The minimum number of edges in a pancyclic graph PDF, 7 pages

  2. Forest Estimate

    Choose at random a set of edges that meets every vertex of a large graph an even number of times. Away from a small marked set, the chosen edges contain no cycle in at most about half of all cases. The two other results use this estimate.

    The forest proportion of a random even subgraph PDF, 12 pages

  3. Exact Maximums

    The rank of a graph is its number of edges minus its number of vertices plus its number of components. For every large rank r, the rings of squares of Horak and Kim have the largest number of cycles. This number is a little more than 2r−1.

    The maximum number of cycles in a graph of large rank PDF, 36 pages