Planar representation of bipartite graphs and the degree of faces

399 Views Asked by At

So the question was the prove by contradiction that $K_3,_3$ is not planar. And so it starts with supposing $K_3,_3$ is planar, and since it has 6 vertices and 9 edges by Euler's formula it must have 5 faces. But then it goes on to say that because $K_3,_3$ is bipartite, none of the faces in its plane representation are triangles- and I got confused. Why is it that planar representations of bipartite graphs have degrees of faces larger than 3?

2

There are 2 best solutions below

1
On

A face must have at least $3$ edges.

If there was a triangular face with vertices $u,v,w$, then $u,v$ would be in different parts of the bipartition, and $v,w$ would also be in different parts, hence $w,u$ would have to be in the same part, contradiction.

Thus, if the graph was planar, every face would have to have more than $3$ edges.

More generally, by an analogous argument, any cycle in a bipartite graph must have even length, so any face must have an even number of edges.

0
On

In a planar drawing of a bipartite graph, the faces have even degrees.

Since $2$ is not a possible face degree, it must be at least $4$.