Dense graphs have minors

Let K 3 , t ∗ denote the graph obtained from K 3 , t by adding all edges between the three vertices of degree t in it. We prove that for each t ≥ 6300 and n ≥ t + 3 , each n -vertex graph G with e ( G ) > 1 2 ( t + 3 ) ( n − 2 ) + 1 has a K 3 , t ∗ -minor. The bound is sharp in the sense that for every t , there are infinitely many graphs G with e ( G ) = 1 2 ( t + 3 ) ( | V ( G ) | − 2 ) + 1 that have no K 3 , t -minor. The result confirms a partial case of the conjecture by Woodall and Seymour that every ( s + t ) -chromatic graph has a K s , t -minor.