Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
To avoid those degree sequences, how about noting that $G$ must have seven vertices because it has a basis i.e. a spanning tree of order $10-4$. This also implies there must be a vertex of even degree: either 4 or 6. – Colin McQuillan Jul 25 '12 at 16:29
Colin, could you please elaborate on that and post it as an answer (I'm a novice concerning graphs and matroids), so that I can set it as the accepted answer? – Pteromys Jul 25 '12 at 23:57
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thanks. Can't this proof be put shorter, by saying that since $G$ has order 7 and has no vertex of degree less than 3, $\sum_{v\in V(G)}\deg (v) \ge 21$, but this quantity should be equal to $2\cdot||K_5|| = 20$? – Pteromys Jul 26 '12 at 5:11
@Pteromys: yes, good observation! – Colin McQuillan Jul 26 '12 at 10:25
You have used two different definitions of the dual graph: one to show that $G$ has order $7$ and the other to show that $\delta(G)\ge 3$. How can one reconcile the two definitions? – Shahab Feb 1 at 1:01

There is a characterisation of (simple) graphs which admits an abstract-dual:

Theorem A graph has an abstract-dual if and only if it is planar.

(For a reference, see Section 8 in An introduction to matroid theory; in particular, the above theorem is the result (G11).)

Since $K_5$ is non-planar, it does not have an abstract-dual.

share|cite|improve this answer
I knew it and was looking for a proof that works specifically for $K_5$. And using the theorem to prove what I want to seems (to me) to be a kind of circular argument, because when you prove the theorem you probably use Wagner's theorem or such things to reduce the general claim about planar graphs to the specific claim about $K_{5}$ and $K_{3,3}$. But anyway, thanks. – Pteromys Jul 25 '12 at 15:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.