Triangle-free Graphs with Large Minimum Common Degree

Let G be a graph. For x∈ V(G), let N(x)=∈ 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\"{a}ggkvist showed that every triangle-free graph with minimum degree greater than 3n/8 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\"{a}ggkvist's result. The balanced blow-up of the M\"{o}bius ladder graph shows that it is best possible.