1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proving a graph not simple and planar after adding edges

  1. Nov 3, 2015 #1
    1. The problem statement, all variables and given/known data

    Prove that no more than 3 edges can be added to G while keeping it planar and simple.
    (The graph in the image is graph G)

    2. Relevant equations
    For a connected, planar, simple graph G, with E edges and V vertices:
    E ≤ 3V - 6

    3. The attempt at a solution
    At first, we have 9 edges, and 6 vertices:

    9 ≤ 3(6) - 6 → 9 ≤ 12

    However, if I just add 4 vertices off to the side, say to the right, and draw four edges connecting them all to vertex E, we'd have 13 edges and 10 vertices.

    13 ≤ 3(10) - 6 → 13 ≤ 24 which is still true.

    Am I misunderstanding one of the definitions in this problem? I'm not quite getting how what I'm doing isn't keeping the graph planar and simple.

    Edit: Clarified equation
  2. jcsd
  3. Nov 3, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It does not say you can add any vertices.
  4. Nov 3, 2015 #3
    Ah, ok, not sure where my assumption that I could came from. So, does it suffice as mathematical proof to just show that:

    9 ≤ 12
    9 + 3 ≤ 12 - is true
    9 + 4 ≤ 12 - is not true

  5. Nov 3, 2015 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. The inequality is necessary but not sufficient. Consider K3,3. It has 9 edges, 6 vertices, but is not planar.
  6. Nov 7, 2015 #5


    User Avatar
    Homework Helper
    Gold Member

    So, any ideas or plan?
    I think the 6 vertices are inviting you to try and show the result of adding more than 3 edges would contain K3,3 which is non-planar.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted