How do you show that the dual of the matroid obtained from the 5-vertex complete graph $K_5$ is not graphic, or equivalently, that $K_5$ has no abstract dual?
I assume graphs considered here are simple.
I (tried to) show it in the following way: to show it by contradiction, let $G$ be an abstract dual graph of $K_5$. Since $K_5$ is 3-edge-connected and thus no cuts (sets of edges whose removal increases the number of components of a graph) of cardinality 3, $G$ has no 3-edge cycle. For each vertex $v$ of $K_5$, consider $H_v$, the set of edges incident to $v$. Since $H_v$ is a minimal cut in $K_5$, it corresponds to a 4-edge cycle in $G$. And because each $H_v$ shares exactly one edge with each of the others, so do the corresponding five 4-edge cycles in $G$. Since a vertex of degree less than 3 in $G$ implies a self-loop or a multiple edge in $K_5$, every vertex in $G$ should have degree greater than or equal to 3. The degree sequences of the (simple) graphs that satisfy the condition should be (4,4,4,4,4), (3,3,3,3,3,5) or (3,3,3,3,4,4). But none of the graphs that have these degree sequences satisfies the condition that it contains five 4-edge cycle each of which shares exactly one edge with each of the others. Contradiction.
I am looking for a proof that doesn't resort to enumeration of a lot of graphs and cycles.
EDIT: I know the characterization of planar graphs pointed out in the Turgeon's answer; I am looking for a proof that works specifically for $K_5$.
Best Answer
The following argument cuts down the cases.
The algebraic dual can be defined as a graph with the same set of edges whose spanning trees are the complement of spanning trees of the original graph. $K_5$ has a spanning tree with four edges, so $G$ has a spanning tree with six edges. Thus $G$ has order seven.
You have shown that $G$ has no 3-cycles and no vertices of degree less than three. There is a unique such graph of order seven: $K_{3,4}$. For example, since $G$ has odd order, it has a vertex $v$ of even degree: four or six. Its neighbours must have degree at least three but cannot be adjacent to each others. This gives a contradicition if $v$ has degree six, and otherwise the neighbours of $v$ must be connected to the remaining two vertices.
But $K_{3,4}$ fails your other condition about 4-cycles.