{"id":462,"date":"2007-07-08T18:48:37","date_gmt":"2007-07-08T18:48:37","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/07\/08\/graph-contraction-and-minors\/"},"modified":"2007-07-08T18:48:37","modified_gmt":"2007-07-08T18:48:37","slug":"graph-contraction-and-minors","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/07\/08\/graph-contraction-and-minors\/","title":{"rendered":"Graph Contraction and Minors"},"content":{"rendered":"

Another useful concept in simple graph theory is *contraction* and its result, *minors*
\nof graphs. The idea is that there are several ways of simplifying a graph in order to study
\nits properties: cutting edges, removing vertices, and decomposing a graph are all methods we’ve seen before. Contraction is a different technique that works by *merging* vertices, rather than removing them.<\/p>\n


\nHere’s how contraction works. Suppose you have a graph G. Pick a pair of vertices v and w
\nwhich are adjacent in G. You can create a graph G’ which is a contraction of G by
\nreplacing v and w with a *single* vertex, and taking any edge in G which is incident on
\neither v or w, and making it incident on the newly contracted node.
\n\"contractor.jpg\"
\nIt’s much clearer
\nin a picture: for example, look at the series of graphs to the right. The first one is
\nthe original graph. Below it, we create a new graph by contracting vertices D and K. D
\nwas adjacent to B, K, and E; K was adjacent to F, G, and D. We *merge* D and K by contracting along the edge connecting them, and the new vertex is adjacent on B, E, F, and G – the union of the adjacencies of D and K.
\nThen we contract again – this time doing two contractions at once – first contracting
\nA,B, and and the merged AB with C. The resulting contracted vertices has the union of the adjacencies of A, B, and C, which are the two vertices DK and F.
\nFinally, we do one more contraction merging H and J.
\nContraction allows us to define a relationship, called *minor*, which can be used to define a partial order over graphs: If we have a graph G, and it can be made isomorphic to a graph
\nH by some series of contractions, then H is called a *minor* of G.
\nThe ordering is based directly on minors: if H is a minor of G, then H≤G.
\nThere are some really interesting theorems that allow us to define
\nproperties of graph structures in terms of minors. For example, there’s
\na theorem called Wagner’s theorem, which says that a graph is planar if and
\nonly if it has neither K5<\/sub> nor K3,3<\/sub> as minors. Let’s look
\nat one example:
\n\"nonplanar-contract.jpg\"
\nWe start with an eight-node non-planar graph. To show that it’s non-planar, we can
\nfirst contract A,B, and then contract E,G – and we end up with K3,3<\/sub>, which
\nmeans that K3,3<\/sub> is a minor of the original, which proves that it’s non-planar.
\nAnother neat theorem involves minors and snarks – and a mistake from a post a couple of days ago. Every snark has Petersen’s graph as a *minor*. (I said *subgraph* the other day.) Of course, it’s not necessarily easy to find the series of contractions. For example,
\nhere’s a nice 20-vertex snark, with the vertices nicely labeled, and a copy of Petersen’s graph next to it. This snark can be contracted to Petersen’s graph in 10 contractions. See if you can figure out which
\nvertex-pairs to contract.
\n\"snark-to-petersen.jpg\"<\/p>\n","protected":false},"excerpt":{"rendered":"

Another useful concept in simple graph theory is *contraction* and its result, *minors* of graphs. The idea is that there are several ways of simplifying a graph in order to study its properties: cutting edges, removing vertices, and decomposing a graph are all methods we’ve seen before. Contraction is a different technique that works by […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-462","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7s","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/462","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=462"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/462\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=462"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=462"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=462"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}