Skip to main content
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
Source Link

First of all, I'm not a mathematician and I hope this question isn't too elementary, but I got no answers on math.SEon 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.

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.

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.

deleted 1 characters in body
Source Link
Jack M
  • 623
  • 3
  • 13

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 non planarbipartite.

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.

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 non planar.

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.

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.

Source Link
Jack M
  • 623
  • 3
  • 13

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 non planar.

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.