0

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.

LaurenceMeister
  • 11
  • 1
    What theorems do you have available to use? How about Kuratowski's theorem? It should be clear that there is a subgraph isomorphic to $K_{3,3}$ within $K_{4,6}$ seen by deleting one of the vertices from the first part and three of the vertices from the second part. – JMoravitz Apr 17 '20 at 17:13
  • Can you use Kuratowski's theorem? – Parcly Taxel Apr 17 '20 at 17:13
  • An alternate route... one can show that for graphs with no cycles of length $3$, that $A\leq 2N-4$ using your notation (or $e\leq 2v-4$ for the more common $e$ for number of edges and $v$ for vertices). Here, $A = 4\times 6 = 24$ is not less than $2\times N - 4 = 16$, so it must be non-planar. You can arrive at this or a similar result simply by modifying your already existing attempt by noting that for a bipartite graph like this, all cycles are of even length and so are strictly of length $4$ or greater rather than just $3$ or greater. – JMoravitz Apr 17 '20 at 17:18
  • Thank you, thats all understood now – LaurenceMeister Apr 18 '20 at 11:14

0 Answers0