MHB Proving a graph is planar/nonplanar

  • Thread starter Thread starter Ragnarok7
  • Start date Start date
  • Tags Tags
    Graph
AI Thread Summary
The discussion revolves around determining the planarity of a complicated graph, which initially satisfies the conditions for planarity but may contain a subgraph homeomorphic to K3,3 or K5, indicating nonplanarity. Participants suggest that simplifying the graph can reveal its nonplanar nature, specifically transforming it into K3,3 through specific edge removals and consolidations. The use of software like CaRMetal is recommended for easier manipulation of graph vertices while maintaining connectivity, which can significantly reduce the time spent on such problems. The process is acknowledged as potentially trial-and-error, but there may be mathematical strategies to streamline it. Ultimately, the graph in question is concluded to be non-coplanar.
Ragnarok7
Messages
50
Reaction score
0
I was given a rather complicated graph as a homework problem, and told to see if it is planar or not. It satisfies the equation $$e\leq 3v-6$$ and has a chromatic number of 4 as well as vertices of degree 5 or below, so there's nothing to rule out planarity there. There are at least 5 vertices of degree 4 or above, and also at least 6 vertices of degree 3 or above, so perhaps it has a subgraph homeomorphic to $$K_{3,3}$$ or $$K_5$$ and so is nonplanar. But I've tried for a long time and I can't get any such subgraph. Is this a trial-and-error process, or is there a better way to go about it?

Thanks!
 
Physics news on Phys.org
Could you please post the graph?
 
I believe this is reducible to $$K_5$$, but I haven't double-checked it yet.

View attachment 1533
 

Attachments

  • Screen Shot 2013-10-21 at 3.42.30 PM.png
    Screen Shot 2013-10-21 at 3.42.30 PM.png
    7.8 KB · Views: 116
It's non-coplanar, but it's not isomorphic to either $K_{5}$ or $K_{3,3}$ directly. However, with a few simplifications, you can actually get it down to $K_{3,3}$. I've attached a picture to show you how:

View attachment 1534

So from the left graph, which is isomorphic to the one you were given, perform the following steps (all of which are simplifications; ergo, if the resulting graph is non-coplanar, then the original must have been non-coplanar.)

1. Remove edge BD.
2. Remove edge AD.
3. Consolidate edges HD and DF into one edge HF.
4. Consolidate edges EC and CG into one edge EG.

The result is the graph on the right, which is $K_{3,3}$. Therefore, your graph is non-coplanar.
 

Attachments

  • NonCoplanar Graph.png
    NonCoplanar Graph.png
    6.7 KB · Views: 113
Thank you so much. It seems easier now that I've had a little more practice, but is it generally just a trial-and-error game?
 
Ragnarok said:
Thank you so much. It seems easier now that I've had a little more practice, but is it generally just a trial-and-error game?

For me it was. There might be some nice mathematical trick to doing it in general. I used software: CaRMetal, a sort of open-source version of Geometer's SketchPad. It allows you to move vertices around easily while retaining the connectivity of the original graph.

What happened with me was this: after trying and trying (and failing, oddly enough) to get the graph to be coplanar, I tried to arranged it in a $K_{3,3}$ fashion. I knew $K_{5}$ wasn't going to be present, because there weren't enough vertices with degree 4 to make it isomorphic. So then it was a matter of grouping two sets of vertices to get both sides of $K_{3,3}$, and after some trial and error, I got it, as you can see. Without CaRMetal or some equivalent software, I'd have spent an enormous amount of time on this problem.
 
Nice! I'll have to check out that software.
 

Similar threads

Replies
3
Views
932
Replies
1
Views
2K
Replies
3
Views
3K
Replies
9
Views
1K
Replies
2
Views
1K
Replies
2
Views
2K
Back
Top