prove that a planer graph has at most 3n-6 edges if n>=3
Answers
As a graph with m≤3n−6 need not be planar (here m is |E(G)| and n=|V(G)|). To answer your question on how to prove that Q3 is planar: simply present a drawing of Q3 in the plane with no edges crossing. this is sufficient to show planarity. If this technique fails (which it won't in this case), one can always show that a K3,3 minor or subdivision is impossible for a given graph along with showing that a K5 minor (or subdivision) is impossible. For example: take any tree and add 3 edges to it, say e1,e2,e3. The resulting graph is still planar. we can prove this in the following way.
Let T be a tree, and let X={e1,e2,e3} be 3 edges not in T. Then T+X is planar. Let m=|E(T)|, and let n=|V(T)|. Then, m′=|E(T)+X|=n−1+3=n+2. Assume, to the contrary, that T+X is non-planar. Then, by Kuratowski's theorem, T+X contains a subdivision of K5 or a subdivision of K3,3. Let s be the number of subdivisions in a graph. Any subdivision of K5 has 5+s vertices and 10+s edges. If our graph does contain a K5 division, then we can find a set of 5+s vertices with 10+s edges between them. Likewise, if our graph contained a subdivision of K3,3 we could find 6+s vertices with 9+s between them. However, any set of 5+s vertices in T+X gives us a maximum of 5+s−1+3=7+s edges between those vertices. Similarly, any set of 6+s vertices in T+X gives us a maximum of 6+s−1+3=8+s edges. In any case, a contradiction is produced, and so it must be the case that T+X is planar.
You could use this example to show that your graph is planar, but as I've said before: it is much more prudent to simply produce a drawing of your graph in the plane with no edges crossing. The technique above works when you don't know exactly what the graph looks like, or need to prove a general result over a specific class of graphs.