Proving K4,6 is non-planar

322 Views Asked by At

I'm trying to prove the graph K4,6 is non planar. Here's what I have so far: Let's assume the graph is planar and hence it satisfies Euler's relationship: R(regions) + N(nodes)=A(arcs)+2. We know N=4+6=10 and A=4x6=24 hence using the above equation R=16. Hence as each region is surrounded by at least 3 arcs A >= (3/2 x 16) hence A is greater than or equal to 24. However this result is true, hence proving nothing really and the reason I am stuck. I understand there must exist one region with at 4 arcs surrounding it however I don't know how I would prove that. Any help would be appreciated.