4
$\begingroup$

First of all, I'm not a mathematician and I hope this question isn't too elementary, but I got no answers on math.SE, and since this is a reference request on a relatively advanced theorem, I thought it might be appropriate to ask here.

I'm looking for a proof of Tutte's theorem on planar graphs:

$G$ is planar if and only if the conflict graph of every cycle in $G$ is bipartite.

The conflict graph of a cycle is, roughly speaking, the set of "chords" on that cycle, with two chords being adjacent in the conflict graph iff they "conflict", in the sense that if both are drawn inside (or both outside) the cycle, then they will necessarily cross.

My textbook gives a reference to this paper, but I can't find the proposition in there. Probably it's expressed in matroid-theoretical language that I just don't understand.

I'd appreciate either a pointer as to which proposition in that paper is the one I want (and some pointers as to how to translate it into graph-theoretical language) or a reference to a graph-theoretical proof of the theorem.

Incidentally, I need a proof that does not rely on Kuratowski's theorem.

Improve this question
$\endgroup$
4
  • $\begingroup$ The paper that you linked to is "A Homotopy Theorem for Matroids, I" and there is - consecutively in the same journal - "A Homotopy Theorem for Matroids, II". In part II, Tutte talks about the excluded minor characterisations for binary and regular matroids (which are proved in this paper) and says they are part of an interesting sequence of four theorems, of which the fourth is Kuratowski's characterization of planar graphs. Nowhere in either paper can I find obvious reference to the conflict graph, but of course Tutte is notoriously difficult to penetrate. $\endgroup$
    – Gordon Royle
    Oct 22, 2013 at 9:22
  • 2
    $\begingroup$ In fact, the result is buried (deep) in the THIRD paper of the series, which is called "Matroid and Graphs" Vol 90 Transactions AMS, 1959, 527-552. $\endgroup$
    – Gordon Royle
    Oct 22, 2013 at 9:37
  • $\begingroup$ @GordonRoyle Thanks very much. Is what Tutte calls an "overlap circuit" the same as a conflict graph? Does "graphic matroid" basically mean "matroid of a planar graph"? If so, is the proposition I'm looking for the one stating "In a graphic matroid every point is even" ? $\endgroup$
    – Jack M
    Oct 22, 2013 at 10:37
  • 1
    $\begingroup$ Graphic matroid is the cycle matroid of a graph. But a graph is planar if the DUAL of its cycle matroid is graphic. I assume that Tutte's "graphicness criterion" when applied to this dual matroid is the criterion you're looking at. But I'd need to look harder to be sure. $\endgroup$
    – Gordon Royle
    Oct 22, 2013 at 12:58

1 Answer 1

Reset to default
3
$\begingroup$

Your condition should say that the conflict graph is bipartite instead of non-planar.
Let me define the conflict graph more precisely and then give a proof. For a cycle $C$ of $G$ a $C$-path is a path $P$ with both of its ends on $V(C)$ but no other vertices on $C$. The vertex set of the conflict graph is the set of $C$-paths, where two $C$-paths $P$ (with ends $p_1$ and $p_2$) and $Q$ (with ends $q_1$ and $q_2$) are adjacent if they do not share any vertices and the cyclic order of their ends is $p_1, q_1, p_2, q_2$ along $C$.

Now, if the conflict graph is not bipartite, then it has an odd cycle $C^*$ of $C$-paths. By the Jordan-Curve Theorem, in any planar drawing of $G$, $C$ bounds a disk $\Delta$ in the plane. But now the vertices of $C^*$ (which are $C$-paths), must alternative between the inside and outside of $\Delta$. But this is impossible since there are an odd number of them. This part does not use Kuratowski's Theorem.

For the other direction suppose $G$ is non-planar. I think Kuratowski's Theorem is unavoidable, so I'll use it. So we either have a subdivision of $K_5$ or $K_{3,3}$. If we have a subdivision of $K_{3,3}$, then let $C$ be a (subdivided) 6-cycle of the subdivision. Then the conflict graph of $G$ with respect to $C$ contains a triangle and is hence not bipartite. If $G$ contains a subdivision of $K_5$, then let $C$ be a (subdivided) 5-cycle of the subdivision. In this case the conflict graph contains a 5-cycle, and is hence also not bipartite.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, the bipartite thing was a typo. The thing is, I was hoping to use Tutte's theorem to prove Kuratowski's theorem, hence the requirement that the proof be independant of Kuratowski. $\endgroup$
    – Jack M
    Oct 22, 2013 at 8:12
  • $\begingroup$ I have a question to the last paragraph. Consider a graph which consists of a hexagon and three antipodal diagonals (i.e. a $K_{3,3}$). Add vertices in the middle of two diagonals, and connect them. Then for the outer 6-cycle $C$, there are two $C$-fragments. How can this example be understood by the last paragraph? $\endgroup$
    – Jaehyeon Seo
    Jun 8, 2020 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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