I am trying to prove that the crossing number of complete graph with 7 vertices is greater than or equal to 7. I know that edges (m)=21 if it is complete, and if the graph were planer 2n = degree of faces, which I think is a minimum of 3 per face. So 2m gte 3f. Based on Euler's formula 3n-3m+3f gte 6 (scaled by 3) then I sub in 2m as 3f and rearrange for m and get m gte 15. If there are 21 edges to begin with and only 15 when it is planer, then 6 edges were removed which means 6 crossing points were removed, however I need to prove that the number of crosses is gte 7 not 6.

I am not sure where I am going wrong/ what I am missing

  • $\begingroup$ Where you go wrong is that just because it is 6 edges away from a planar graph, it does not mean that adding them back will only create 6 crossings. They can (and will) create more crossings. $\endgroup$ – JimN Dec 9 '17 at 6:29
  • $\begingroup$ hmm ok thank you, I see what you are saying. How do I figure out how many crossings it would create or do I need a whole new approach? Thank you. $\endgroup$ – Abby29 Dec 9 '17 at 18:18
  • $\begingroup$ Normally when I see crossing numbers given in a course, the lesson includes some bounds on crossing numbers derived from v-e+f relationships (very similar to your own). Did you get any equations or inequalities on crossing numbers? Or a proof for K6 or anything similar? $\endgroup$ – JimN Dec 9 '17 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.