Triangle-free Graphs with Large Minimum Common Degree

Let G be a graph. For x V (G), let N (x) =\y V (G) xy E (G) \. The minimum common degree of G, denoted by ₂ (G), is defined as the minimum of |N (x) N (y) | over all non-edges xy of G. In 1982, H\"aggkvist showed that every triangle-free graph with minimum degree greater than 3n8 is homomorphic to a cycle of length 5. In this paper, we prove that every triangle-free graph with minimum common degree greater than 8 is homomorphic to a cycle of length 5, which implies H\"aggkvist's result. The balanced blow-up of the M\"obius ladder graph shows that it is best possible.