Is it possible to partition k8 into 2 planar subgraphs?

Any help would be appreciated.

Here is a theorem relating the number of edges to the number of vertices in a planar graph: .
In there are 28 edges. If you partition that graph into two subgraph you get where .
Now try for a contradiction.

Thank you very much for your help.

I am not quite sure about that answer since you dont necesserally have 28 edges for your 2 subgraphs.
And I (think) have found a example when it works:
-k4 and k4

Quote:

Originally Posted by arnaud89 I am not quite sure about that answer since you dont necesserally have 28 edges for your 2 subgraphs.

Yes you do have all 28 edges.
The question says to partition into two subgraphs.
I assume that is using the term partition in the standard way.

can you not delete some edges when partitioning your graph??

and why does k4 doesnt work?

thanks

No you cannot.
Do you know what it means to have a partition of a set?
In this case, the partition has two cells, nonempty, disjoint and their union is the graph.

yes I understand that. But surely a subgraph G of H is obtained by deleting some vertices and/or edges.
so if it cut k8 in the middle , i delete all the crossing edges and i am left with the complete graph on four vertices which is planar.

Whats wrong with that argument?
thanks.

Are you left with two disjoint subgraphs such that their union is ?

K_8 has 28 edges k_4 + k_4 has 6+6 12 edges

let the graph k_8 have vertices x1,x2,x3,x4,x5,x6,x7,x8

consider a
First graph k_4 with x1,x2,x3,x4 and the edges from x1,x2,x3 to the vertices x5,x6 and x4 to x7,x8

second graph k_4 with x5,x6,x7,x8 and the edges x4 to the vertices x5,x6 and the edges x1,x2,x3 to x7,x8

my email id 140580@gmail.com