I am trying to prove what the maximum number of edges that can be added to the petersen graph is without changing the crossing number of 2.

  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Dec 9 '17 at 6:01
  • $\begingroup$ I have tried drawing it and can add 8, but I know there are more and this would be an example not a proof. I have also tried calculating it by thinking that if I add more edges the degree of each face would be at least 3. This means 2m lte 3f (m-edges, f-faces). so put it this in rulers equation and scaling it so there is a 3f I'd have 3n-3m+3f gte 6, I then subbed 2m in as 3f to get m lte 3n-6 so m lte 24. If there are currently 15 edges in the graph I can add x amount more subtract 2 (since there are 2 crossings) =24, so I can add 11 edges. I am not sure if this makes any sense though. $\endgroup$ – Abby29 Dec 9 '17 at 18:23

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.