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

1. Nov 3, 2015

### cmkluza

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. Nov 3, 2015

### haruspex

It does not say you can add any vertices.

3. Nov 3, 2015

### cmkluza

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

Thanks!

4. Nov 3, 2015

### haruspex

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

5. Nov 7, 2015

### epenguin

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.