0

After learning some very useful Graph Theory in this question (What is the correct term for cycles more fundamental than Simple Cycles?), I realized that in my work I have been considering a conjecture, which I would like to know if it is a theorem.

Has this been proven? For planar graphs, any edge of an undirected cyclic graph may participate in a maximum of two faces.

Can anyone confirm or correct me?

Community
  • 1
philologon
  • 215

2 Answers2

1

Each interior edge of a planar graph is incident with exactly 2 faces. Each exterior edge is incident with at most 2 faces.

Laars Helenius
  • 7,965
  • 1
  • 23
  • 35
  • What are "interior" and "exterior" edges? – Josh Apr 11 '17 at 00:37
  • An interior edge is not incident with the exterior face. The exterior face is all the space outside the graph. – Laars Helenius Apr 11 '17 at 00:51
  • Then I believe your answer is not right, an interior edge can be incident with exactly one face. – Josh Apr 11 '17 at 15:12
  • An interior edge is an orientable curve. It has two sides, each side is a distinct face. The only way an interior edge can touch exactly one face is if it is part of a path that extends into a face without being incident with any other vertices adjacent to the face. – Laars Helenius Apr 11 '17 at 16:59
  • I'm not sure I understand you. An edge (interior or exterior) is the image of a continuous map from $[0,1]$ to the plane. It has no two sides to speak of. I also don't understand your last sentence. Is the letter Q not an example of a graph that has an edge (the "tail" of Q) incident to exactly one face, i.e. the outer one? If you put the tail inside the circle it then becomes incident to only the inner face. – Josh Apr 11 '17 at 20:34
1

Yes, given a planar embedding of a planar graph, every edge is incident to at most two faces. Cyclicity of the graph doesn't really have anything to do with it.

The Jordan curve theorem is often quoted as justification for this statement, but exact details are often left out in most texts that I have seen, probably because the proof is rather quite fiddly and more topology than graph theory proper.

If you really want to see a proof written out, Combinatorial Optimization by Korte and Vygen has one. (Although even there it's rather sketchy, and also only proves the statement for 2-connected planar graphs, in which case every edge is incident to exactly two faces.)

Josh
  • 2,539