How to prove the statement?

Question

Counts

There is a graph with n vertices, where 3 < n < 8. There is also an additional graph of this graph (i.e. a graph with the same vertices from the original graph, which has edges that are not in the original graph). How to prove that at least one of them is planar?

Answer 1

See the criteria for planarity - you have to dance from them.
For example, if we take the first criterion, the graph does not contain a sub-harf, which is a subdivision of K5 or K3,3.
It is obvious that n=4 the graph itself is always planar. There is nothing to prove. There are cases n=5,6,7.
If the graph itself does not contain such a graph, then it is already planar, there is nothing to prove. If the graph itself contains K5 or K3,3 then you need to prove that the complementary graph cannot contain such subgraphs.
n=8, obviously, does not fit here, because you can take K5, screw K3 next to it (Without new edges between clicks). In this case, the additional graph will be K5,3 - which contains K3,3.
I advise you to consider 3 cases and prove that they are not all possible. The graph and the additional graph each contain K5; both contain K3,3; one contains K5 and the other K3,3.
For example, the first case is quite simple - for n<8 subgraphs intersect at least 3 vertices. In the direct graph, due to K5 they must have edges between them, and because of K5 in the complementary graph, they must not have edges between them. Contradiction.