{"id":2337,"date":"2015-11-11T11:42:30","date_gmt":"2015-11-11T16:42:30","guid":{"rendered":"http:\/\/sites.williams.edu\/Morgan\/?p=2337"},"modified":"2015-11-11T11:45:08","modified_gmt":"2015-11-11T16:45:08","slug":"eulers-theorem-by-induction-on-vertices","status":"publish","type":"post","link":"https:\/\/sites.williams.edu\/Morgan\/2015\/11\/11\/eulers-theorem-by-induction-on-vertices\/","title":{"rendered":"Euler&#8217;s Theorem by Induction on Vertices"},"content":{"rendered":"<p>In my Discrete Math class today, Ryan Patton asked to prove Euler\u2019s circuit theorem by induction on the number of vertices. Alex Summers contributed an idea about pairing\/short-cutting instead of removing the edges incident to a deleted vertex. The class came up with the following proof. Is this proof out there somewhere?<\/p>\n<p><strong>Theorem<\/strong> (Euler). <em>A pseudograph has a circuit containing all edges and vertices if it is connected and every vertex has even degree.<\/em><\/p>\n<p>Proof by induction on the number <em>n<\/em> of vertices.<\/p>\n<p>Base case <em>n<\/em>=1. Just follow the loops in succession.<\/p>\n<p>Now assume for <em>n<\/em> and prove for a pseudo-graph of <em>n<\/em>+1 vertices. Pick a vertex. Since degree even, you can pair the incident edges, and you can avoid pairing the two ends of a loop. Short-cut each pair to avoid the vertex and delete it. By induction, each component of the new pseudo-graph has the desired circuit. Now restore the vertex and undo the short cuts to obtain the desired circuit.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In my Discrete Math class today, Ryan Patton asked to prove Euler\u2019s circuit theorem by induction on the number of vertices. Alex Summers contributed an idea about pairing\/short-cutting instead of removing the edges incident to a deleted vertex. The class came up with the following proof. Is this proof out there somewhere? Theorem (Euler). A [&hellip;]<\/p>\n","protected":false},"author":269,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[15425,14043],"tags":[],"class_list":["post-2337","post","type-post","status-publish","format-standard","hentry","category-education","category-math"],"acf":[],"_links":{"self":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/2337","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/users\/269"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/comments?post=2337"}],"version-history":[{"count":4,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/2337\/revisions"}],"predecessor-version":[{"id":2341,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/2337\/revisions\/2341"}],"wp:attachment":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/media?parent=2337"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/categories?post=2337"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/tags?post=2337"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}