These fields are all optional and need only be supplied if you would like a direct reply. Subject Your email address Your real name

You must answer this! If you don't, my spam filtering will ensure that I never see your email. What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.
File: AnotherProofOfTheDoodleTheorem ''' <link rel="alternate" type="application/rss+xml" ''' href="/rss.xml" title="RSS Feed"> ********> width="25%" |>> ''' <a title="Subscribe to my feed" ''' rel="alternate" ''' href="https://www.solipsys.co.uk/rss.xml"> ''' <img style="border-width: 0px;" ''' src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png" ''' align="middle" ''' alt="" />Subscribe!</a> _ ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> <<| ---- My latest posts can be found here: * ColinsBlog ---- Previous blog posts: * WhenObviousIsNotObvious * GraphThreeColouring * TheDoodleTheorem * BeCarefulWhatYouSay * TheMutilatedChessboardRevisited * AMirrorCopied * TheOtherOtherRopeAroundTheEarth * PhotocopyAMirror * ThePointOfTheBanachTarskiTheorem * SieveOfEratosthenesInPython * FastPerrinTest * RussianPeasantMultiplication * FindingPerrinPseudoPrimes_Part2 * FindingPerrinPseudoPrimes_Part1 * TheUnwiseUpdate * MilesPerGallon * TrackingAnItemOnHackerNews * HackerNewsUserAges * PokingTheDustyCorners * ThereIsNoTimeForThis * PublicallySharingLinks * LearningTimesTables * GracefulDegradation * DiagrammingMathsTopics * OnTheRack * SquareRootByLongDivision * BeyondTheBoundary * FillInTheGaps * SoftwareChecklist * NASASpaceCrews * TheBirthdayParadox * TheTrapeziumConundrum * RevisitingTheAnt * TheAntAndTheRubberBand * IrrationalsExist * MultipleChoiceProbabilityPuzzle * RandomEratosthenes * WrappingUpSquareDissection * DissectingASquarePart2 * DissectingACircle * DissectingASquare * AnOddityInTennis * DecisionTreeForTennis * DecisionTreesInGames * AMatterOfConvention * DoYouNourishOrTarnish * BinarySearchReconsidered * TwoEqualsFour * TheLostPropertyOffice * TheForgivingUserInterface * SettingUpRSS * WithdrawingFromHackerNews ---- Additionally, some earlier writings: * RandomWritings. * ColinsBlog2010 * ColinsBlog2009 * ColinsBlog2008 * ColinsBlog2007 * ColinsBlogBefore2007 ''' <img src="/cgi-bin/CountHits.py?AnotherProofOfTheDoodleTheorem" alt="" /> ******** [[[>40 For a bit more context about this the page on GraphThreeColouring might help. This page has been TaggedAsMaths. ]]] So on theDoodleTheorem page we have a proof of, yes, you guessed it, the Doodle Theorem. Here, on a page entitled Another Proof of the Doodle Theorem we have, yes, you guessed it, another proof of the Doodle Theorem. TheDoodleTheorem says: ''' <table> ''' <tr> ''' <td width="25%"> ''' </td> ''' <td width="50%"> Any map drawn with a single pen stroke that returns to its starting point can be two-coloured. ''' </td> ''' <td width="25%"> ''' </td> ''' </tr> ''' </table> [[[>50 Note that you're not allowed to retrace your steps (as it were), and draw over a line already drawn. Formally, an EulerCycle is a list of vertices from the graph, with repeats, such that the first is the same as the last (hence "cycle") and such that every edge appears exactly once. In this way, visiting each vertex in that order results in a drawing of the graph. ]]] So a graph that can be drawn with a single pen stroke is, by construction, planar, connected, and has an EulerCycle. TheDoodleTheorem is saying that the dual of such a graph is bi-partite. It must be admitted that this is not a deep theorem, and of itself it's not especially important. However, it's a nice introduction to graph theory, and significantly less well known than the usual Koenigsberg problem. But there are several important concepts, and completely accessible. So here is an alternate proof. !! Our opening gambit We claim the following: ''' <table> ''' <tr> ''' <td width="25%"> ''' </td> ''' <td width="50%"> A graph that can be drawn wth a single pen stroke that returns to its starting point, can also be drawn without crossing over a line already drawn. ''' </td> ''' <td width="25%"> ''' </td> ''' </tr> ''' </table> [[[> https://www.solipsys.co.uk/images/CrossingLines.png ]]] In other words, a planar, connected, Eulerian graph (that is, has an EulerCycle) can be drawn such that the situation here never happens. Here we are part way through drawing our graph, and we are approaching a vertex, only to find that we have to cross over a line that already exists. [[[< https://www.solipsys.co.uk/images/ExplodedVertex.png ]]] So here's an example of what a vertex has to look like. We've exploded the vertex to show how the drawing proceeds. It doesn't matter which colours were drawn first, and it doesn't matter which direction we were travelling when we drew each colour, what matters is that they never cross each other during the drawing process. [[[> https://www.solipsys.co.uk/images/EulerFail.png ]]] Here is an example of a graph that can be drawn, and we are part way through an attempt to draw it which will fail. The theorem here claims that this never need happen. So how do we prove this? Remarkably, the proof is almost identical to the usual proof that every graph such that every vertex has even degree is Eulerian, we just need to carry the extra condition with us. ! Proof We proceed by induction. Suppose $G$ is connected, planar, and every vertex has even degree. Suppose further that every graph satisfying those conditions but which has fewer edges can be drawn without crossing a previously drawn line. Let $F$ be any face in $G$, and remove its edges, giving $G-F$. Certainly what is left is planar, and at every vertex it either has its original complement of edges, and so an even number, or two edges have been removed, so it's /still/ an even number. So each component of $G-F$ is connected, planar, and has no odd degree vertices. So by our inductive hypothesis every component of $G-F$ can be drawn as required with no crossing lines. [[[< https://www.solipsys.co.uk/images/VisitingAVertex.png ]]] Now begin drawing $F,$ proceeding clockwise. Whenever we visit a vertex $v$ in a component of $G-F$ not yet drawn, run around that (using our inductive hypothesis that we can draw it with no crossing lines) starting with the edge that is immediately clockwise from the edge in $F$ just drawn. [[[>40 This require some justification, but a few pictures of the different cases will soon convince the reader. A complete and detailed description of all the cases is more work than is really warranted. ]]] When we return to $v$ we can continue around $F$ as required. By continuing around $F$ and ignoring vertices that have already been drawn we complete the entire traversal of $G$, as required. It remains only to consider the induction base case(s). Ignoring the case of the single isolated vertex, the base case is a single vertex with a single loop, which clearly can be drawn without crossing any lines. And so we are done. !! Using the new result [[[< https://www.solipsys.co.uk/images/ExplodedVertices.png ]]] Now we can draw our graph, but gently explode each vertex so that one pair of edges that come in then out as we draw them don't touch the other edges. Here's an example. We can see now that our EulerCycle is basically a distorted circle - it's a simple closed curve. As such, by the Jordan Curve Theorem (or in this case simply by common sense) we can see that it has an inside and an outside. [[[> https://www.solipsys.co.uk/images/BiColouring.png ]]] Colour the inside one colour, and the outside the other colour. This gives us a bi-colouring of the original planar graph. Thus we have shown that any connected, planar graph with an EulerCycle can be two-coloured. That is, its dual is bi-partite. And we're done. ---- |>> | |>> <<<< Prev <<<< ---- WhenObviousIsNotObvious <<| | : | |>> >>>> Next >>>> ---- FactoringViaGraphThreeColouring ... <<| | ---- ********> ''' <a href="https://twitter.com/ColinTheMathmo">You should follow me on twitter</a> ******** ''' <a href="https://twitter.com/ColinTheMathmo"> ''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png" ''' title="By: TwitterButtons.net" ''' width="212" height="69" ''' alt="@ColinTheMathmo" ''' /></a> ********< <<| ---- !! Comments I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semi-automated system. That's looking increasingly unlikely. ********<