Dense graphs have K3,tK3,t minors

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