2 color theorem











up vote
5
down vote

favorite
1












Remember 4 color theorem: any map in a plane can be colored with 4 colors so that no two adjacent regions have the same color.



Draw a map: Put your pen to paper, start from a point P and draw a continuous line and return to P again. Do not redraw any part of the line but intersection is allowed.



All maps I drew in this way can be colored with 2 colors so that no two adjacent regions have the same color.



can you find a counterexample or do you know any theorems in graph theory about such maps?



(all I know about graph theory is what I remember from highschool.)





Edit:



Let M be a map which can be colored with 2 colors so that no two adjacent regions have the same color. Can M be drawn as described above?










share|cite|improve this question
























  • You mean I pick an arbitrary graph, start from an arbitrary point, draw a line an come back, and look at the new graph?
    – Anon
    Feb 1 '13 at 1:53










  • Oh I got it now, you start from a blank paper but your line can self-intersect :)
    – Anon
    Feb 1 '13 at 1:54










  • yes____________
    – user59671
    Feb 1 '13 at 1:55










  • The 4 color theorem states that any map on the plane can be 4-colored. It might take more than 4 colors to color a map on, say, the surface of a bagel (where you need 7 for some maps).
    – Rick Decker
    Feb 1 '13 at 2:10










  • fixed----------------
    – user59671
    Feb 1 '13 at 2:13















up vote
5
down vote

favorite
1












Remember 4 color theorem: any map in a plane can be colored with 4 colors so that no two adjacent regions have the same color.



Draw a map: Put your pen to paper, start from a point P and draw a continuous line and return to P again. Do not redraw any part of the line but intersection is allowed.



All maps I drew in this way can be colored with 2 colors so that no two adjacent regions have the same color.



can you find a counterexample or do you know any theorems in graph theory about such maps?



(all I know about graph theory is what I remember from highschool.)





Edit:



Let M be a map which can be colored with 2 colors so that no two adjacent regions have the same color. Can M be drawn as described above?










share|cite|improve this question
























  • You mean I pick an arbitrary graph, start from an arbitrary point, draw a line an come back, and look at the new graph?
    – Anon
    Feb 1 '13 at 1:53










  • Oh I got it now, you start from a blank paper but your line can self-intersect :)
    – Anon
    Feb 1 '13 at 1:54










  • yes____________
    – user59671
    Feb 1 '13 at 1:55










  • The 4 color theorem states that any map on the plane can be 4-colored. It might take more than 4 colors to color a map on, say, the surface of a bagel (where you need 7 for some maps).
    – Rick Decker
    Feb 1 '13 at 2:10










  • fixed----------------
    – user59671
    Feb 1 '13 at 2:13













up vote
5
down vote

favorite
1









up vote
5
down vote

favorite
1






1





Remember 4 color theorem: any map in a plane can be colored with 4 colors so that no two adjacent regions have the same color.



Draw a map: Put your pen to paper, start from a point P and draw a continuous line and return to P again. Do not redraw any part of the line but intersection is allowed.



All maps I drew in this way can be colored with 2 colors so that no two adjacent regions have the same color.



can you find a counterexample or do you know any theorems in graph theory about such maps?



(all I know about graph theory is what I remember from highschool.)





Edit:



Let M be a map which can be colored with 2 colors so that no two adjacent regions have the same color. Can M be drawn as described above?










share|cite|improve this question















Remember 4 color theorem: any map in a plane can be colored with 4 colors so that no two adjacent regions have the same color.



Draw a map: Put your pen to paper, start from a point P and draw a continuous line and return to P again. Do not redraw any part of the line but intersection is allowed.



All maps I drew in this way can be colored with 2 colors so that no two adjacent regions have the same color.



can you find a counterexample or do you know any theorems in graph theory about such maps?



(all I know about graph theory is what I remember from highschool.)





Edit:



Let M be a map which can be colored with 2 colors so that no two adjacent regions have the same color. Can M be drawn as described above?







graph-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Feb 1 '13 at 2:21

























asked Feb 1 '13 at 1:47







user59671



















  • You mean I pick an arbitrary graph, start from an arbitrary point, draw a line an come back, and look at the new graph?
    – Anon
    Feb 1 '13 at 1:53










  • Oh I got it now, you start from a blank paper but your line can self-intersect :)
    – Anon
    Feb 1 '13 at 1:54










  • yes____________
    – user59671
    Feb 1 '13 at 1:55










  • The 4 color theorem states that any map on the plane can be 4-colored. It might take more than 4 colors to color a map on, say, the surface of a bagel (where you need 7 for some maps).
    – Rick Decker
    Feb 1 '13 at 2:10










  • fixed----------------
    – user59671
    Feb 1 '13 at 2:13


















  • You mean I pick an arbitrary graph, start from an arbitrary point, draw a line an come back, and look at the new graph?
    – Anon
    Feb 1 '13 at 1:53










  • Oh I got it now, you start from a blank paper but your line can self-intersect :)
    – Anon
    Feb 1 '13 at 1:54










  • yes____________
    – user59671
    Feb 1 '13 at 1:55










  • The 4 color theorem states that any map on the plane can be 4-colored. It might take more than 4 colors to color a map on, say, the surface of a bagel (where you need 7 for some maps).
    – Rick Decker
    Feb 1 '13 at 2:10










  • fixed----------------
    – user59671
    Feb 1 '13 at 2:13
















You mean I pick an arbitrary graph, start from an arbitrary point, draw a line an come back, and look at the new graph?
– Anon
Feb 1 '13 at 1:53




You mean I pick an arbitrary graph, start from an arbitrary point, draw a line an come back, and look at the new graph?
– Anon
Feb 1 '13 at 1:53












Oh I got it now, you start from a blank paper but your line can self-intersect :)
– Anon
Feb 1 '13 at 1:54




Oh I got it now, you start from a blank paper but your line can self-intersect :)
– Anon
Feb 1 '13 at 1:54












yes____________
– user59671
Feb 1 '13 at 1:55




yes____________
– user59671
Feb 1 '13 at 1:55












The 4 color theorem states that any map on the plane can be 4-colored. It might take more than 4 colors to color a map on, say, the surface of a bagel (where you need 7 for some maps).
– Rick Decker
Feb 1 '13 at 2:10




The 4 color theorem states that any map on the plane can be 4-colored. It might take more than 4 colors to color a map on, say, the surface of a bagel (where you need 7 for some maps).
– Rick Decker
Feb 1 '13 at 2:10












fixed----------------
– user59671
Feb 1 '13 at 2:13




fixed----------------
– user59671
Feb 1 '13 at 2:13










4 Answers
4






active

oldest

votes

















up vote
5
down vote



accepted










I assume that during the drawing process you do not allow retracing of part of a line that's already been drawn. If you do then there is a counterexample.



If you don't allow that then observe that every vertex of the graph has even degree because as you drew you had to pass in to that vertex exactly as many times as you passed out.



Using that fact one can show that the result can in fact be 2-colored.






share|cite|improve this answer





















  • Couldn't have said it better myself.
    – Joe Z.
    Feb 1 '13 at 1:59












  • yes do not redraw part of a line. I'll fix my post.
    – user59671
    Feb 1 '13 at 2:00










  • Maybe I'm missing something obvious, but this answer seems a little too terse. The cycle on $3$ vertices has all even-degree vertices, but is not $2$-colourable.
    – Rahul
    Feb 1 '13 at 2:08






  • 1




    @$Bbb{R^n}$: But its dual graph is!
    – Micah
    Feb 1 '13 at 2:13










  • @$mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP.
    – Jim
    Feb 1 '13 at 2:13




















up vote
4
down vote













Re the edit: No. For example, a map consisting of several concentric circles is $2$-colorable, but can't be drawn as you're describing.



However, if you add in the condition that your boundaries all connect to each other, the answer becomes "yes", by Euler's famous Königsberg bridge solution.






share|cite|improve this answer




























    up vote
    1
    down vote













    The 2-colorable graphs are bipartite graphs: a graph is bipartite iff it is 2-colorable.






    share|cite|improve this answer




























      up vote
      0
      down vote













      (I know this thread is years old, but I thought maybe somebody might still be interested in that proof you were asking for.)



      I think if you relax the requirement of drawing a single closed geometrical shape in the way you describe (without lifting the pen and without drawing on top of existing line segments), but also allow multiple such shapes (no matter if it crosses itself and/or any of the perhaps already existing lines), then I think indeed any 2-colorable graph can be drawn like this.



      But first I start with the (perhaps more interesting?) "=>"-direction: "If a graph is drawn in the way as described above, it is always 2-colorable."



      People have already realised, that the Graph G, where the line intersections are the vertices, and line segments connecting two vertices are edges, is an Euler graph, because obviously, all vertices have even degree (intersecting a line creates a new vertex with degree 4, crossing an already existing vertex adds 2 to its degree), and we can assume (without losing generality), that the graph is connected (if it's not, the following proof applies to each connected sub-graph analogously).



      Also, it is obvious to see, that a bipartite graph is always 2-colorable (first partition of vertices: color 1, second partition: color 2). So what's left to be shown is, that if a planar graph G is Eulerian, then its dual graph G' is always bipartite (and therefore 2-colorable, obviously).



      [I hereby show a contradiction proof, which uses the property, that the dual of a dual Graph should be isomorphic to the original Graph, so G'' = G. The proof idea was taken from Jorge Fernandez: Prove that the graph dual to Eulerian planar graph is bipartite. ]



      Let's assume G is Eulerian, but G' is NOT bipartite. Since it is not bipartite, it contains at least one odd cycle (cycle with an odd number of vertices). The proof for this is rather straight-forward (and can be found on youtube...). If we could show, that this Graph G' contains at least one face with an odd number of adjacent edges, this means that G'' is NOT Eulerian, because the respective vertex in G'' representing that face in G' will have odd degree! -- On the other side, it MUST be Eulerian, because it is isomorphic to G, which is Eulerian as to our assumption. => contradiction of the assumption.



      So what remains to be shown is, that a graph containing at least one odd cycle always contains such a face with an odd number of adjacent edges. Let's have a look at one of the odd cycles in G' (it contains at least one such cycle, so let's just pick any). Since G' is planar (because G is), I think it is valid here to talk about things being "outside" or "inside" the cycle. We are only looking here at things inside that odd cycle "C". So let's look at our odd cycle C, and distinguish between the following two cases:



      (1) Inside of C, there are no edges or vertices. That means we have found a face with an odd number of adjacent edges (the cycle surrounds that face) --> FINISHED.



      (2) Inside of C, there is some cycle-free path P=[i,a1,a2,...,j], connecting two vertices i and j of the cycle. [It could as well just be P=[i,j], so a direct edge from i to j, splitting our cycle in two parts.] So let's split C along that path P, yielding two cycles C1 and C2. What is the total number of vertices |C1|+|C2| now? Well, i and j have to be counted twice now, as they are contained in both new cycles, and the same holds for the intermediate vertices (if any) a1,a2,... So: |C1|+|C2|=|C|+2*|P|. Apparently, this sum does not change the parity: If |C| was odd, then also |C1|+|C2| is odd, and therefore either |C1| or |C2| must be odd. We now choose the odd cycle, and start over with this cycle.



      We can be sure, that this process terminates after a finite number of steps (if the number of edges is finite), finally "finding" an odd-edged face, because the number of edges enclosed in C will reduce in each step. Further, from the statements above it is clear that there is always an odd-cycle (we can never end up with two even cycles after the splitting step).



      Discussion: I think from the way how we created G', there are no more special cases to examine. For example, isolated vertices, or vertices inside C which are connected to C only via a single connection, are impossible from the way how G' was constructed: This would mean, that G' is not a map, and so G'' would not be defined, I guess (but it must be, because G=G''). [Does anybody have a counter-example? Are there any special cases that I forgot?] There are examples without cycles in G' at all, but then of course we are looking at a tree, which is obviously bipartite, which is against our assumption.)



      The reverse direction "<=": "A two-colorable graph can always be drawn as indicated above (allowing multiple closed planar shapes)." [Micah commented on this already, I just repeat his solution with my own words]



      The dual graph G' of a two-colorable graph G is always bipartite. [Again: this is just obvious.] A bipartite graph is known to contain only even cycles. This is already known to be equivalent to the Euler property if we assume, that the graph is connected. If the graph is not connected (but consists of multiple connected components G1', G2', ...), the above statement holds for each components individually, meaning that each conponent fulfills the Euler property -- and thus, each component can be drawn without lifting the pen, and without drawing on top of an already existing line.






      share|cite|improve this answer























      • You did a really nice job answering this question; I'd encourage you to expand by answering newer questions.
        – Tianlalu
        Nov 22 at 11:15











      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f291844%2f2-color-theorem%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown
























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      5
      down vote



      accepted










      I assume that during the drawing process you do not allow retracing of part of a line that's already been drawn. If you do then there is a counterexample.



      If you don't allow that then observe that every vertex of the graph has even degree because as you drew you had to pass in to that vertex exactly as many times as you passed out.



      Using that fact one can show that the result can in fact be 2-colored.






      share|cite|improve this answer





















      • Couldn't have said it better myself.
        – Joe Z.
        Feb 1 '13 at 1:59












      • yes do not redraw part of a line. I'll fix my post.
        – user59671
        Feb 1 '13 at 2:00










      • Maybe I'm missing something obvious, but this answer seems a little too terse. The cycle on $3$ vertices has all even-degree vertices, but is not $2$-colourable.
        – Rahul
        Feb 1 '13 at 2:08






      • 1




        @$Bbb{R^n}$: But its dual graph is!
        – Micah
        Feb 1 '13 at 2:13










      • @$mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP.
        – Jim
        Feb 1 '13 at 2:13

















      up vote
      5
      down vote



      accepted










      I assume that during the drawing process you do not allow retracing of part of a line that's already been drawn. If you do then there is a counterexample.



      If you don't allow that then observe that every vertex of the graph has even degree because as you drew you had to pass in to that vertex exactly as many times as you passed out.



      Using that fact one can show that the result can in fact be 2-colored.






      share|cite|improve this answer





















      • Couldn't have said it better myself.
        – Joe Z.
        Feb 1 '13 at 1:59












      • yes do not redraw part of a line. I'll fix my post.
        – user59671
        Feb 1 '13 at 2:00










      • Maybe I'm missing something obvious, but this answer seems a little too terse. The cycle on $3$ vertices has all even-degree vertices, but is not $2$-colourable.
        – Rahul
        Feb 1 '13 at 2:08






      • 1




        @$Bbb{R^n}$: But its dual graph is!
        – Micah
        Feb 1 '13 at 2:13










      • @$mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP.
        – Jim
        Feb 1 '13 at 2:13















      up vote
      5
      down vote



      accepted







      up vote
      5
      down vote



      accepted






      I assume that during the drawing process you do not allow retracing of part of a line that's already been drawn. If you do then there is a counterexample.



      If you don't allow that then observe that every vertex of the graph has even degree because as you drew you had to pass in to that vertex exactly as many times as you passed out.



      Using that fact one can show that the result can in fact be 2-colored.






      share|cite|improve this answer












      I assume that during the drawing process you do not allow retracing of part of a line that's already been drawn. If you do then there is a counterexample.



      If you don't allow that then observe that every vertex of the graph has even degree because as you drew you had to pass in to that vertex exactly as many times as you passed out.



      Using that fact one can show that the result can in fact be 2-colored.







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered Feb 1 '13 at 1:57









      Jim

      24.2k23270




      24.2k23270












      • Couldn't have said it better myself.
        – Joe Z.
        Feb 1 '13 at 1:59












      • yes do not redraw part of a line. I'll fix my post.
        – user59671
        Feb 1 '13 at 2:00










      • Maybe I'm missing something obvious, but this answer seems a little too terse. The cycle on $3$ vertices has all even-degree vertices, but is not $2$-colourable.
        – Rahul
        Feb 1 '13 at 2:08






      • 1




        @$Bbb{R^n}$: But its dual graph is!
        – Micah
        Feb 1 '13 at 2:13










      • @$mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP.
        – Jim
        Feb 1 '13 at 2:13




















      • Couldn't have said it better myself.
        – Joe Z.
        Feb 1 '13 at 1:59












      • yes do not redraw part of a line. I'll fix my post.
        – user59671
        Feb 1 '13 at 2:00










      • Maybe I'm missing something obvious, but this answer seems a little too terse. The cycle on $3$ vertices has all even-degree vertices, but is not $2$-colourable.
        – Rahul
        Feb 1 '13 at 2:08






      • 1




        @$Bbb{R^n}$: But its dual graph is!
        – Micah
        Feb 1 '13 at 2:13










      • @$mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP.
        – Jim
        Feb 1 '13 at 2:13


















      Couldn't have said it better myself.
      – Joe Z.
      Feb 1 '13 at 1:59






      Couldn't have said it better myself.
      – Joe Z.
      Feb 1 '13 at 1:59














      yes do not redraw part of a line. I'll fix my post.
      – user59671
      Feb 1 '13 at 2:00




      yes do not redraw part of a line. I'll fix my post.
      – user59671
      Feb 1 '13 at 2:00












      Maybe I'm missing something obvious, but this answer seems a little too terse. The cycle on $3$ vertices has all even-degree vertices, but is not $2$-colourable.
      – Rahul
      Feb 1 '13 at 2:08




      Maybe I'm missing something obvious, but this answer seems a little too terse. The cycle on $3$ vertices has all even-degree vertices, but is not $2$-colourable.
      – Rahul
      Feb 1 '13 at 2:08




      1




      1




      @$Bbb{R^n}$: But its dual graph is!
      – Micah
      Feb 1 '13 at 2:13




      @$Bbb{R^n}$: But its dual graph is!
      – Micah
      Feb 1 '13 at 2:13












      @$mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP.
      – Jim
      Feb 1 '13 at 2:13






      @$mathbb R^n$: "Vertices" here means any self crossing in the line drawn by the OP.
      – Jim
      Feb 1 '13 at 2:13












      up vote
      4
      down vote













      Re the edit: No. For example, a map consisting of several concentric circles is $2$-colorable, but can't be drawn as you're describing.



      However, if you add in the condition that your boundaries all connect to each other, the answer becomes "yes", by Euler's famous Königsberg bridge solution.






      share|cite|improve this answer

























        up vote
        4
        down vote













        Re the edit: No. For example, a map consisting of several concentric circles is $2$-colorable, but can't be drawn as you're describing.



        However, if you add in the condition that your boundaries all connect to each other, the answer becomes "yes", by Euler's famous Königsberg bridge solution.






        share|cite|improve this answer























          up vote
          4
          down vote










          up vote
          4
          down vote









          Re the edit: No. For example, a map consisting of several concentric circles is $2$-colorable, but can't be drawn as you're describing.



          However, if you add in the condition that your boundaries all connect to each other, the answer becomes "yes", by Euler's famous Königsberg bridge solution.






          share|cite|improve this answer












          Re the edit: No. For example, a map consisting of several concentric circles is $2$-colorable, but can't be drawn as you're describing.



          However, if you add in the condition that your boundaries all connect to each other, the answer becomes "yes", by Euler's famous Königsberg bridge solution.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Feb 1 '13 at 2:48









          Micah

          29.5k1363104




          29.5k1363104






















              up vote
              1
              down vote













              The 2-colorable graphs are bipartite graphs: a graph is bipartite iff it is 2-colorable.






              share|cite|improve this answer

























                up vote
                1
                down vote













                The 2-colorable graphs are bipartite graphs: a graph is bipartite iff it is 2-colorable.






                share|cite|improve this answer























                  up vote
                  1
                  down vote










                  up vote
                  1
                  down vote









                  The 2-colorable graphs are bipartite graphs: a graph is bipartite iff it is 2-colorable.






                  share|cite|improve this answer












                  The 2-colorable graphs are bipartite graphs: a graph is bipartite iff it is 2-colorable.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Feb 1 '13 at 2:02









                  ashley

                  79049




                  79049






















                      up vote
                      0
                      down vote













                      (I know this thread is years old, but I thought maybe somebody might still be interested in that proof you were asking for.)



                      I think if you relax the requirement of drawing a single closed geometrical shape in the way you describe (without lifting the pen and without drawing on top of existing line segments), but also allow multiple such shapes (no matter if it crosses itself and/or any of the perhaps already existing lines), then I think indeed any 2-colorable graph can be drawn like this.



                      But first I start with the (perhaps more interesting?) "=>"-direction: "If a graph is drawn in the way as described above, it is always 2-colorable."



                      People have already realised, that the Graph G, where the line intersections are the vertices, and line segments connecting two vertices are edges, is an Euler graph, because obviously, all vertices have even degree (intersecting a line creates a new vertex with degree 4, crossing an already existing vertex adds 2 to its degree), and we can assume (without losing generality), that the graph is connected (if it's not, the following proof applies to each connected sub-graph analogously).



                      Also, it is obvious to see, that a bipartite graph is always 2-colorable (first partition of vertices: color 1, second partition: color 2). So what's left to be shown is, that if a planar graph G is Eulerian, then its dual graph G' is always bipartite (and therefore 2-colorable, obviously).



                      [I hereby show a contradiction proof, which uses the property, that the dual of a dual Graph should be isomorphic to the original Graph, so G'' = G. The proof idea was taken from Jorge Fernandez: Prove that the graph dual to Eulerian planar graph is bipartite. ]



                      Let's assume G is Eulerian, but G' is NOT bipartite. Since it is not bipartite, it contains at least one odd cycle (cycle with an odd number of vertices). The proof for this is rather straight-forward (and can be found on youtube...). If we could show, that this Graph G' contains at least one face with an odd number of adjacent edges, this means that G'' is NOT Eulerian, because the respective vertex in G'' representing that face in G' will have odd degree! -- On the other side, it MUST be Eulerian, because it is isomorphic to G, which is Eulerian as to our assumption. => contradiction of the assumption.



                      So what remains to be shown is, that a graph containing at least one odd cycle always contains such a face with an odd number of adjacent edges. Let's have a look at one of the odd cycles in G' (it contains at least one such cycle, so let's just pick any). Since G' is planar (because G is), I think it is valid here to talk about things being "outside" or "inside" the cycle. We are only looking here at things inside that odd cycle "C". So let's look at our odd cycle C, and distinguish between the following two cases:



                      (1) Inside of C, there are no edges or vertices. That means we have found a face with an odd number of adjacent edges (the cycle surrounds that face) --> FINISHED.



                      (2) Inside of C, there is some cycle-free path P=[i,a1,a2,...,j], connecting two vertices i and j of the cycle. [It could as well just be P=[i,j], so a direct edge from i to j, splitting our cycle in two parts.] So let's split C along that path P, yielding two cycles C1 and C2. What is the total number of vertices |C1|+|C2| now? Well, i and j have to be counted twice now, as they are contained in both new cycles, and the same holds for the intermediate vertices (if any) a1,a2,... So: |C1|+|C2|=|C|+2*|P|. Apparently, this sum does not change the parity: If |C| was odd, then also |C1|+|C2| is odd, and therefore either |C1| or |C2| must be odd. We now choose the odd cycle, and start over with this cycle.



                      We can be sure, that this process terminates after a finite number of steps (if the number of edges is finite), finally "finding" an odd-edged face, because the number of edges enclosed in C will reduce in each step. Further, from the statements above it is clear that there is always an odd-cycle (we can never end up with two even cycles after the splitting step).



                      Discussion: I think from the way how we created G', there are no more special cases to examine. For example, isolated vertices, or vertices inside C which are connected to C only via a single connection, are impossible from the way how G' was constructed: This would mean, that G' is not a map, and so G'' would not be defined, I guess (but it must be, because G=G''). [Does anybody have a counter-example? Are there any special cases that I forgot?] There are examples without cycles in G' at all, but then of course we are looking at a tree, which is obviously bipartite, which is against our assumption.)



                      The reverse direction "<=": "A two-colorable graph can always be drawn as indicated above (allowing multiple closed planar shapes)." [Micah commented on this already, I just repeat his solution with my own words]



                      The dual graph G' of a two-colorable graph G is always bipartite. [Again: this is just obvious.] A bipartite graph is known to contain only even cycles. This is already known to be equivalent to the Euler property if we assume, that the graph is connected. If the graph is not connected (but consists of multiple connected components G1', G2', ...), the above statement holds for each components individually, meaning that each conponent fulfills the Euler property -- and thus, each component can be drawn without lifting the pen, and without drawing on top of an already existing line.






                      share|cite|improve this answer























                      • You did a really nice job answering this question; I'd encourage you to expand by answering newer questions.
                        – Tianlalu
                        Nov 22 at 11:15















                      up vote
                      0
                      down vote













                      (I know this thread is years old, but I thought maybe somebody might still be interested in that proof you were asking for.)



                      I think if you relax the requirement of drawing a single closed geometrical shape in the way you describe (without lifting the pen and without drawing on top of existing line segments), but also allow multiple such shapes (no matter if it crosses itself and/or any of the perhaps already existing lines), then I think indeed any 2-colorable graph can be drawn like this.



                      But first I start with the (perhaps more interesting?) "=>"-direction: "If a graph is drawn in the way as described above, it is always 2-colorable."



                      People have already realised, that the Graph G, where the line intersections are the vertices, and line segments connecting two vertices are edges, is an Euler graph, because obviously, all vertices have even degree (intersecting a line creates a new vertex with degree 4, crossing an already existing vertex adds 2 to its degree), and we can assume (without losing generality), that the graph is connected (if it's not, the following proof applies to each connected sub-graph analogously).



                      Also, it is obvious to see, that a bipartite graph is always 2-colorable (first partition of vertices: color 1, second partition: color 2). So what's left to be shown is, that if a planar graph G is Eulerian, then its dual graph G' is always bipartite (and therefore 2-colorable, obviously).



                      [I hereby show a contradiction proof, which uses the property, that the dual of a dual Graph should be isomorphic to the original Graph, so G'' = G. The proof idea was taken from Jorge Fernandez: Prove that the graph dual to Eulerian planar graph is bipartite. ]



                      Let's assume G is Eulerian, but G' is NOT bipartite. Since it is not bipartite, it contains at least one odd cycle (cycle with an odd number of vertices). The proof for this is rather straight-forward (and can be found on youtube...). If we could show, that this Graph G' contains at least one face with an odd number of adjacent edges, this means that G'' is NOT Eulerian, because the respective vertex in G'' representing that face in G' will have odd degree! -- On the other side, it MUST be Eulerian, because it is isomorphic to G, which is Eulerian as to our assumption. => contradiction of the assumption.



                      So what remains to be shown is, that a graph containing at least one odd cycle always contains such a face with an odd number of adjacent edges. Let's have a look at one of the odd cycles in G' (it contains at least one such cycle, so let's just pick any). Since G' is planar (because G is), I think it is valid here to talk about things being "outside" or "inside" the cycle. We are only looking here at things inside that odd cycle "C". So let's look at our odd cycle C, and distinguish between the following two cases:



                      (1) Inside of C, there are no edges or vertices. That means we have found a face with an odd number of adjacent edges (the cycle surrounds that face) --> FINISHED.



                      (2) Inside of C, there is some cycle-free path P=[i,a1,a2,...,j], connecting two vertices i and j of the cycle. [It could as well just be P=[i,j], so a direct edge from i to j, splitting our cycle in two parts.] So let's split C along that path P, yielding two cycles C1 and C2. What is the total number of vertices |C1|+|C2| now? Well, i and j have to be counted twice now, as they are contained in both new cycles, and the same holds for the intermediate vertices (if any) a1,a2,... So: |C1|+|C2|=|C|+2*|P|. Apparently, this sum does not change the parity: If |C| was odd, then also |C1|+|C2| is odd, and therefore either |C1| or |C2| must be odd. We now choose the odd cycle, and start over with this cycle.



                      We can be sure, that this process terminates after a finite number of steps (if the number of edges is finite), finally "finding" an odd-edged face, because the number of edges enclosed in C will reduce in each step. Further, from the statements above it is clear that there is always an odd-cycle (we can never end up with two even cycles after the splitting step).



                      Discussion: I think from the way how we created G', there are no more special cases to examine. For example, isolated vertices, or vertices inside C which are connected to C only via a single connection, are impossible from the way how G' was constructed: This would mean, that G' is not a map, and so G'' would not be defined, I guess (but it must be, because G=G''). [Does anybody have a counter-example? Are there any special cases that I forgot?] There are examples without cycles in G' at all, but then of course we are looking at a tree, which is obviously bipartite, which is against our assumption.)



                      The reverse direction "<=": "A two-colorable graph can always be drawn as indicated above (allowing multiple closed planar shapes)." [Micah commented on this already, I just repeat his solution with my own words]



                      The dual graph G' of a two-colorable graph G is always bipartite. [Again: this is just obvious.] A bipartite graph is known to contain only even cycles. This is already known to be equivalent to the Euler property if we assume, that the graph is connected. If the graph is not connected (but consists of multiple connected components G1', G2', ...), the above statement holds for each components individually, meaning that each conponent fulfills the Euler property -- and thus, each component can be drawn without lifting the pen, and without drawing on top of an already existing line.






                      share|cite|improve this answer























                      • You did a really nice job answering this question; I'd encourage you to expand by answering newer questions.
                        – Tianlalu
                        Nov 22 at 11:15













                      up vote
                      0
                      down vote










                      up vote
                      0
                      down vote









                      (I know this thread is years old, but I thought maybe somebody might still be interested in that proof you were asking for.)



                      I think if you relax the requirement of drawing a single closed geometrical shape in the way you describe (without lifting the pen and without drawing on top of existing line segments), but also allow multiple such shapes (no matter if it crosses itself and/or any of the perhaps already existing lines), then I think indeed any 2-colorable graph can be drawn like this.



                      But first I start with the (perhaps more interesting?) "=>"-direction: "If a graph is drawn in the way as described above, it is always 2-colorable."



                      People have already realised, that the Graph G, where the line intersections are the vertices, and line segments connecting two vertices are edges, is an Euler graph, because obviously, all vertices have even degree (intersecting a line creates a new vertex with degree 4, crossing an already existing vertex adds 2 to its degree), and we can assume (without losing generality), that the graph is connected (if it's not, the following proof applies to each connected sub-graph analogously).



                      Also, it is obvious to see, that a bipartite graph is always 2-colorable (first partition of vertices: color 1, second partition: color 2). So what's left to be shown is, that if a planar graph G is Eulerian, then its dual graph G' is always bipartite (and therefore 2-colorable, obviously).



                      [I hereby show a contradiction proof, which uses the property, that the dual of a dual Graph should be isomorphic to the original Graph, so G'' = G. The proof idea was taken from Jorge Fernandez: Prove that the graph dual to Eulerian planar graph is bipartite. ]



                      Let's assume G is Eulerian, but G' is NOT bipartite. Since it is not bipartite, it contains at least one odd cycle (cycle with an odd number of vertices). The proof for this is rather straight-forward (and can be found on youtube...). If we could show, that this Graph G' contains at least one face with an odd number of adjacent edges, this means that G'' is NOT Eulerian, because the respective vertex in G'' representing that face in G' will have odd degree! -- On the other side, it MUST be Eulerian, because it is isomorphic to G, which is Eulerian as to our assumption. => contradiction of the assumption.



                      So what remains to be shown is, that a graph containing at least one odd cycle always contains such a face with an odd number of adjacent edges. Let's have a look at one of the odd cycles in G' (it contains at least one such cycle, so let's just pick any). Since G' is planar (because G is), I think it is valid here to talk about things being "outside" or "inside" the cycle. We are only looking here at things inside that odd cycle "C". So let's look at our odd cycle C, and distinguish between the following two cases:



                      (1) Inside of C, there are no edges or vertices. That means we have found a face with an odd number of adjacent edges (the cycle surrounds that face) --> FINISHED.



                      (2) Inside of C, there is some cycle-free path P=[i,a1,a2,...,j], connecting two vertices i and j of the cycle. [It could as well just be P=[i,j], so a direct edge from i to j, splitting our cycle in two parts.] So let's split C along that path P, yielding two cycles C1 and C2. What is the total number of vertices |C1|+|C2| now? Well, i and j have to be counted twice now, as they are contained in both new cycles, and the same holds for the intermediate vertices (if any) a1,a2,... So: |C1|+|C2|=|C|+2*|P|. Apparently, this sum does not change the parity: If |C| was odd, then also |C1|+|C2| is odd, and therefore either |C1| or |C2| must be odd. We now choose the odd cycle, and start over with this cycle.



                      We can be sure, that this process terminates after a finite number of steps (if the number of edges is finite), finally "finding" an odd-edged face, because the number of edges enclosed in C will reduce in each step. Further, from the statements above it is clear that there is always an odd-cycle (we can never end up with two even cycles after the splitting step).



                      Discussion: I think from the way how we created G', there are no more special cases to examine. For example, isolated vertices, or vertices inside C which are connected to C only via a single connection, are impossible from the way how G' was constructed: This would mean, that G' is not a map, and so G'' would not be defined, I guess (but it must be, because G=G''). [Does anybody have a counter-example? Are there any special cases that I forgot?] There are examples without cycles in G' at all, but then of course we are looking at a tree, which is obviously bipartite, which is against our assumption.)



                      The reverse direction "<=": "A two-colorable graph can always be drawn as indicated above (allowing multiple closed planar shapes)." [Micah commented on this already, I just repeat his solution with my own words]



                      The dual graph G' of a two-colorable graph G is always bipartite. [Again: this is just obvious.] A bipartite graph is known to contain only even cycles. This is already known to be equivalent to the Euler property if we assume, that the graph is connected. If the graph is not connected (but consists of multiple connected components G1', G2', ...), the above statement holds for each components individually, meaning that each conponent fulfills the Euler property -- and thus, each component can be drawn without lifting the pen, and without drawing on top of an already existing line.






                      share|cite|improve this answer














                      (I know this thread is years old, but I thought maybe somebody might still be interested in that proof you were asking for.)



                      I think if you relax the requirement of drawing a single closed geometrical shape in the way you describe (without lifting the pen and without drawing on top of existing line segments), but also allow multiple such shapes (no matter if it crosses itself and/or any of the perhaps already existing lines), then I think indeed any 2-colorable graph can be drawn like this.



                      But first I start with the (perhaps more interesting?) "=>"-direction: "If a graph is drawn in the way as described above, it is always 2-colorable."



                      People have already realised, that the Graph G, where the line intersections are the vertices, and line segments connecting two vertices are edges, is an Euler graph, because obviously, all vertices have even degree (intersecting a line creates a new vertex with degree 4, crossing an already existing vertex adds 2 to its degree), and we can assume (without losing generality), that the graph is connected (if it's not, the following proof applies to each connected sub-graph analogously).



                      Also, it is obvious to see, that a bipartite graph is always 2-colorable (first partition of vertices: color 1, second partition: color 2). So what's left to be shown is, that if a planar graph G is Eulerian, then its dual graph G' is always bipartite (and therefore 2-colorable, obviously).



                      [I hereby show a contradiction proof, which uses the property, that the dual of a dual Graph should be isomorphic to the original Graph, so G'' = G. The proof idea was taken from Jorge Fernandez: Prove that the graph dual to Eulerian planar graph is bipartite. ]



                      Let's assume G is Eulerian, but G' is NOT bipartite. Since it is not bipartite, it contains at least one odd cycle (cycle with an odd number of vertices). The proof for this is rather straight-forward (and can be found on youtube...). If we could show, that this Graph G' contains at least one face with an odd number of adjacent edges, this means that G'' is NOT Eulerian, because the respective vertex in G'' representing that face in G' will have odd degree! -- On the other side, it MUST be Eulerian, because it is isomorphic to G, which is Eulerian as to our assumption. => contradiction of the assumption.



                      So what remains to be shown is, that a graph containing at least one odd cycle always contains such a face with an odd number of adjacent edges. Let's have a look at one of the odd cycles in G' (it contains at least one such cycle, so let's just pick any). Since G' is planar (because G is), I think it is valid here to talk about things being "outside" or "inside" the cycle. We are only looking here at things inside that odd cycle "C". So let's look at our odd cycle C, and distinguish between the following two cases:



                      (1) Inside of C, there are no edges or vertices. That means we have found a face with an odd number of adjacent edges (the cycle surrounds that face) --> FINISHED.



                      (2) Inside of C, there is some cycle-free path P=[i,a1,a2,...,j], connecting two vertices i and j of the cycle. [It could as well just be P=[i,j], so a direct edge from i to j, splitting our cycle in two parts.] So let's split C along that path P, yielding two cycles C1 and C2. What is the total number of vertices |C1|+|C2| now? Well, i and j have to be counted twice now, as they are contained in both new cycles, and the same holds for the intermediate vertices (if any) a1,a2,... So: |C1|+|C2|=|C|+2*|P|. Apparently, this sum does not change the parity: If |C| was odd, then also |C1|+|C2| is odd, and therefore either |C1| or |C2| must be odd. We now choose the odd cycle, and start over with this cycle.



                      We can be sure, that this process terminates after a finite number of steps (if the number of edges is finite), finally "finding" an odd-edged face, because the number of edges enclosed in C will reduce in each step. Further, from the statements above it is clear that there is always an odd-cycle (we can never end up with two even cycles after the splitting step).



                      Discussion: I think from the way how we created G', there are no more special cases to examine. For example, isolated vertices, or vertices inside C which are connected to C only via a single connection, are impossible from the way how G' was constructed: This would mean, that G' is not a map, and so G'' would not be defined, I guess (but it must be, because G=G''). [Does anybody have a counter-example? Are there any special cases that I forgot?] There are examples without cycles in G' at all, but then of course we are looking at a tree, which is obviously bipartite, which is against our assumption.)



                      The reverse direction "<=": "A two-colorable graph can always be drawn as indicated above (allowing multiple closed planar shapes)." [Micah commented on this already, I just repeat his solution with my own words]



                      The dual graph G' of a two-colorable graph G is always bipartite. [Again: this is just obvious.] A bipartite graph is known to contain only even cycles. This is already known to be equivalent to the Euler property if we assume, that the graph is connected. If the graph is not connected (but consists of multiple connected components G1', G2', ...), the above statement holds for each components individually, meaning that each conponent fulfills the Euler property -- and thus, each component can be drawn without lifting the pen, and without drawing on top of an already existing line.







                      share|cite|improve this answer














                      share|cite|improve this answer



                      share|cite|improve this answer








                      edited Nov 22 at 11:03

























                      answered Nov 22 at 10:50









                      David

                      11




                      11












                      • You did a really nice job answering this question; I'd encourage you to expand by answering newer questions.
                        – Tianlalu
                        Nov 22 at 11:15


















                      • You did a really nice job answering this question; I'd encourage you to expand by answering newer questions.
                        – Tianlalu
                        Nov 22 at 11:15
















                      You did a really nice job answering this question; I'd encourage you to expand by answering newer questions.
                      – Tianlalu
                      Nov 22 at 11:15




                      You did a really nice job answering this question; I'd encourage you to expand by answering newer questions.
                      – Tianlalu
                      Nov 22 at 11:15


















                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f291844%2f2-color-theorem%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Ellipse (mathématiques)

                      Quarter-circle Tiles

                      Mont Emei