Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza

Abstract Erdős et al. (1989) [4] conjectured that the diameter of a K 2 r -free connected graph of order n and minimum degree δ ≥ 2 is at most 2 ( r − 1 ) ( 3 r + 2 ) ( 2 r 2 − 1 ) ⋅ n δ + O ( 1 ) for every r ≥ 2 , if δ is a multiple of ( r − 1 ) ( 3 r + 2 ) . For every r > 1 and δ ≥ 2 ( r − 1 ) , we create K 2 r -free graphs with minimum degree δ and diameter ( 6 r − 5 ) n ( 2 r − 1 ) δ + 2 r − 3 + O ( 1 ) , which are counterexamples to the conjecture for every r > 1 and δ > 2 ( r − 1 ) ( 3 r + 2 ) ( 2 r − 3 ) .