Trying to prove: Subgraph of a planar graph is also a planar graph

Iva

New member
Joined
Mar 11, 2018
Messages
4
Hi!
I've been trying to prove that the subgraph of a planar graph is also a planar graph. It seems really intuitive but I can't work it out on paper. I've been trying to use Euler's formula v-e+r=2 where v is the number of vertices, e is the number of edges and r is the number of regions, but I can't generalize it so that it works for any subgraph of a given planar graph. Does anyone have any suggestions or hints?
Thanks in advance.
 
Hi!
I've been trying to prove that the subgraph of a planar graph is also a planar graph. It seems really intuitive but I can't work it out on paper. I've been trying to use Euler's formula v-e+r=2 where v is the number of vertices, e is the number of edges and r is the number of regions, but I can't generalize it so that it works for any subgraph of a given planar graph. Does anyone have any suggestions or hints?
Thanks in advance.

Why can't you start with the definition of a planar graph, rather than Euler's formula? If a graph can be embedded in a plane, isn't that necessarily true of any subgraph (since all you are doing is removing parts of it)? And if you don't know if the subgraph is planar, how can you even talk about the number of regions? They are defined in terms of the plane it lies in!

Please tell us more about the context of the question. What definitions are you using?
 
Top