Minimum C 5 ‐saturated graphs

A graph is C 5 ‐saturated if it has no five‐cycle as a subgraph, but does contain a C 5 after the addition of any new edge. We prove that the minimum number of edges in a C 5 ‐saturated graph on n ≥11 vertices is sat ( n, C 5 )=⌈10( n −1)/7⌉−1 if n ∈ N 0 ={11, 12, 13, 14, 16, 18, 20} and is ⌈10( n −1)/7⌉ if n ≥11 and n ∉ N 0 . © 2009 Wiley Periodicals, Inc. J Graph Theory