Proving that a bipartite graph, of minimum degree $4$, doesn't contain $K_{3,3}$

198 Views Asked by At

Prove that a bipartite graph, of minimum degree $4$, doesn't necessarily contain $K_{3,3}$

I know I just need a counter example, but I'm having some extreme difficulty finding one.

1

There are 1 best solutions below

1
On

If you're looking for a bipartite graph with minimum degree $4$ which doesn't contain $K_{3,3}$, then here's one:

Bipartite example

The different coloured edges are just for clarity, it's a messy drawing.