In class we noted that every nonplanar graph contains an edg

In class we noted that every non-planar graph contains an edge so that if we erase this edge then the crossing number of the new graph is smaller. Is there a graph such that no matter which edge is deleted the crossing number of the new graph is smaller? Is there a graph such that no matter which edge is deleted the crossing number of the new graph reduces by two or more?

Solution

Yes

the complete graph with 4 vertices is planar... Draw a triangle, draw a vertex in the middle of the triangle. Include the remaining edges