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: TheDoodleTheorem ''' <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: * 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?TheDoodleTheorem" alt="" /> ******** [[[> This page has _ been TaggedAsMaths. ]]] !!! The Doodle Theorem The Doodle Theorem says: ''' <table> ''' <tr> ''' <td width="20%"> ''' </td> ''' <td width="60%"> [[[ Any map drawn with a single pen stroke that returns to its starting point can be two-coloured. ]]] ''' </td> ''' <td width="20%"> ''' </td> ''' </tr> ''' </table> Here's one proof. [[[> https://www.solipsys.co.uk/images/DoodleExample.png ]]] Take a planar graph that's been drawn with a single pen stroke that returns to its starting point. * As we draw the graph, for every vertex we must arrive, then depart. * Except for the vertex where we start and end, but we can think of the final arrival as matched with the initial departure. * As a result, every vertex must have an even number of edges. * In the dual, a circuit around a vertex of the original will have an even number of edges, * ... because edges in the dual cross edges in the original. [[[> https://www.solipsys.co.uk/images/CombiningCycles.png ]]] * Consider two circuits that share edges but do not cross. When combined into a single cycle, the length of the resulting cycle is the sum of the two lengths, minus twice the number of edges in the shared section. * By combining the individual cycles in the dual around vertices of the original map, we can now see that /every/ cycle in the dual is of even length. Now we use the theorem that says: * A graph is bipartite if and only if every circuit is even. We'll come back to that in a minute. [[[>50 An EulerCycle is a tour of all the edges of a graph, visiting vertices as often as necessary, but traversing every edge exactly once, and returning to our starting position. ]]] So given all that, we now have that the dual is bipartite, and that means both it and the original map can be bi-coloured! So we're done - a planar graph with an EulerCycle (see side box) can be bi-coloured. Well, nearly done. We still have to show that last step. ''' <table cellpadding="5" cellspacing="10" border="1"> ''' <tr> <td valign="top" width="25%"> *_Theorem:_* * A graph is bipartite * /if/and/only/if/ * Every circuit is even. ''' </td><td> *_Proof:_* It's enough to prove this for each component, so we may assume that the graph is connected. Pick any vertex $a$ and put it in $A.$ Repeatedly pick a vertex $v$ in $A$ and put its neighbours in $B,$ or pick a vertex in $B$ and put its neighbours in $A.$ If a vertex is put both in $A$ and in $B$ (for the first time), that gives us an odd cycle. If this never happens, then the sets $A$ and $B$ form a partition of the vertices of the graph into two independent sets; in other words, it is a bipartite graph. And we really are done. ''' </td> </tr> </table> ---- |>> | |>> <<<< Prev <<<< ---- BeCarefulWhatYouSay <<| | : | |>> >>>> Next >>>> ---- GraphThreeColouring ... <<| | ---- ********> ''' <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. ********<