e(ho0n3 Posted September 15, 2004 Share Posted September 15, 2004 Here is a simple statement which I've yet to prove satisfactorily: Adding/deleting loops, parallel edges and edges in series does not affect the planarity of a graph. If a graph is planar, then removing anything from it does not create any edge crossings, so the graph remains planar. If a graph is not planar, then adding anything to it will or will not create any edge crosssings, so the graph remains unplanar. Now I have to show that adding (removing) loops, parallel edges and edges in series does not affect the planarity of a(n) planar (unplanar respectively) graph. This is were I stopped. I'm trying to think of a good argument which shows that a planar graph remains planar after the addition of loops. I'm guessing I'll have to describe a process that can add loops without creating edge crossings. Any tips? Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now