Is there a graph-theoretical proof of Tutte's theorem on matroids? 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.
 A: 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.  
