Planar graph K3,3

228 Views Asked by At

I need a little help with graphs in the field of graph theory.

I have 3 undirected graphs :
A1 = {{x1, x2, x3, x4, x5, x6, x7, x8}, {{x1, x2}, {x1, x3}, {x1, x8}, {x2, x6}, {x2, x7 }, {x3, x4}, {x3, x5}, {x3, x8}, {x4, x7}, {x5, x6}, {x5, x7}, {x5, x8}, {x6, x7}, {x6, x8}}}

A2 = {{x1, x2, x3, x4, x5, x6, x7, x8}, {{x1, x2}, {x1, x7}, {x2, x3}, {x2, x6}, {x2, x8 }, {x3, x4}, {x3, x8}, {x4, x5}, {x4, x7}, {x5, x6}, {x5, x7}, {x5, x8}, {x6, x7}, {x6, x8}}}

A3 = {{x1, x2, x3, x4, x5, x6, x7, x8}, {{x1, x2}, {x1, x5}, {x1, x8}, {x2, x3}, {x2, x7 }, {x3, x4}, {x3, x5}, {x3, x6}, {x4, x5}, {x4, x7}, {x4, x8}, {x5, x7}, {x6, x8}, {x7, x8}}}

The situation is as follows: I examined the isomorphism and planarity of the graphs and I got the following results: A1 is isomorphic to A2, A1 is not isomorphic to A3, A2 is not isomorphic to A3. I managed to draw A1 and A2 it can be drawn in such a way that no edges cross each other. Which means that A1 and A2 are planar but A3 is not. I also tested all this using python algorithms and the networkx library. But graph A3 is not planar and I know it is not, but trying to make K3,3 I can't do it at all, does anyone have an idea from you how I could do it?

This is graph A3 This is A3

1

There are 1 best solutions below

0
On BEST ANSWER

In the graph $A_3$ remove vertex $x_6$ but add edge $x_3x_8$. Remove vertex $x_4$. The result is $K_{3,3}$. Its parts are $\{1,3,7\}$ and $\{2,5,8\}$.