- Thread starter
- #1

Thanks!

- Thread starter Ragnarok
- Start date

- Thread starter
- #1

Thanks!

- Admin
- #2

- Jan 26, 2012

- 4,197

Could you please post the graph?

- Thread starter
- #3

- Admin
- #4

- Jan 26, 2012

- 4,197

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.

- Thread starter
- #5

- Admin
- #6

- Jan 26, 2012

- 4,197

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.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?

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.

- Thread starter
- #7