Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application. (Q1853125)

We show that an \(n\)-vertex bipartite \(K_{3,3}\)-free graph with \(n\geqslant3\) has at most \(2n-4\) edges and that an \(n\)-vertex bipartite \(K_{5}\)-free graph with \(n\geqslant5\) has at most \(3n-9\) edges. These bounds are also tight. We then use the bound on the number of edges in a \(K_{3,3}\)-free graph to extend two known NC algorithms for planar graphs to \(K_{3,3}\)-free graphs.