{"id":460,"date":"2007-07-03T15:49:04","date_gmt":"2007-07-03T15:49:04","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/07\/03\/edge-coloring-and-graph-turning\/"},"modified":"2007-07-03T15:49:04","modified_gmt":"2007-07-03T15:49:04","slug":"edge-coloring-and-graph-turning","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/07\/03\/edge-coloring-and-graph-turning\/","title":{"rendered":"Edge Coloring and Graph Turning"},"content":{"rendered":"

In addition to doing vertex and face colorings of a graph, you can also do edge colorings. In an edge coloring, no two edges which are incident on the same vertex can share the same color. In general, edge coloring doesn’t get as much attention as vertex coloring or face coloring, but it can be an interesting subject. Today I’m going to show you an example of a really clever visual proof technique called *graph turning* to prove a statement about the edge colorings of complete graphs.
\nJust like a graph has a chromatic index for its vertex coloring, it’s got a chromatic
\nindex for its edge coloring. The edge chromatic index of a graph G is the minimum number of colors in any edge-coloring of G. The theorem that I’m going to prove for you is about the edge chromatic index of complete graphs with 2n vertices for some integer n:
\n**The edge-chromatic index of a complete graph K2n<\/sub> = 2n-1.**<\/p>\n


\nTo start with, we’ll set an *lower bound* on the value of the edge-chromatic index, which is simple. The edge chromatic index of a graph is greater than or equal to the highest
\ndegree of any vertex in that graph. The reason why is obvious by definition: the edge coloring must have distinct colors for any edges that are incident on the same vertex – so any coloring wit less colors than the degree of some vertex *must* necessarily have two edges of that vertex with the same color.
\nIn fact, we can be even stronger than that for regular graphs. For a n-regular graph (that is, a graph where every vertex has *n* edges), the edge-chromatic index must be either n or n+1.
\nEvery vertex in K2n<\/sub> is degree 2n-1. So to prove the theorem, all we need to do is show that there is an edge coloring with degree 2n-1.
\n\"k10.jpg\"
\nThe way that we’ll do that is using a technique called graph turning. Take the graph, and pick one vertex. Call it vertex *X*, which we’ll use as the *pivot* of the turning. Take the other vertices, and number them from 0 to 2n-2. (As a running example down the right, we’ll use K10<\/sub> – K2n<\/sub> for n=5, which must have a coloring with 9 colors.)
\nTo do the turning, you set up the graph as follows:
\n\"k10-turn0.jpg\"
\n* Drag the pivot out of the graph. Put vertex 0 to the left of it. Then in two columns under it, put 1, 2, 3, … on the right side under the pivot, and 2n-2, 2n-3, …. on the left, with the two columns
\nlining up in rows. (See the example to the side.) This two column structure, with
\nX at the top of the right-hand column, is what we’ll use for turning.
\n* Take this initial configuration, with X and 0 at the top. Each horizontal edge is
\ngoing to get color 0. So 0→x, 2n-2→1, 2n-3→2, and so on, get color 0.
\n(In our example, it’s (0,x), (8,1), (7,2), (6,3), (5,4)).)
\n\"k10-turn1.jpg\"
\n* Now we’re going to *turn* the graph. Keep the pivot where it is, but rotate all of the
\nother vertices counterclockwise – so now 1 is paired with X, 0 is lined up with 2, 2n-2
\nis lined up with with 3, and so on. Now, all of the edges that are horizontal get color 1.
\n\"k10-turn2.jpg\"
\n* Turn again: X gets paired with 2, 1 with 3, 0 with 4, 2n-2 with 5; again, the horizontals get the next color, color 2.
\nEach turning of the graph will select a new set of N edges to be colored. How many times can we turn it? Each node 0 through 2n-1 (that is, 2n+1 nodes) will get paired with X – there are 2n-2 turns, assigning 2n-1 colors (the initial color, plus one for each turning). If you look at the example diagrams, you can see that the colored edges can’t get to the horizontal where they’d be colored in less that 2n-1 turns. So this produces a coloring with 2n-1 colors. Since we already know that the edge-coloring has *at least* 2n-1 colors, we’ve proved that the chromatic index is exactly 2n-1, because it can be colored in that minimum.
\nThen, as a simple corollary, we can show that a complete graph with 2n-1 vertices *also* has edge chromatic index 2n-1. It’s really easy. There are two parts to the proof: first, showing that the graph *can* be edge-colored in 2n-1 colors; and then showing that it *can’t* be edge-colored in 2n-2 colors.
\nTo show that it can be edge-colored in 2n-1 colors, we can just add another vertex, turning it into K2n<\/sub>, coloring it as above, and then removing the extra vertex, keeping the colors of the edges.
\nTo show that it *can’t* be edge-colored in 2n-2 colors, there’s a simple combinatorial trick we can use:
\n* The complete graph with 2n-1 vertices has ((2n-1) choose 2) edges, or (2n-1)(n-1)=2n2<\/sup>-3n+1 edges.
\n* Suppose that we *could* color all of the edges with 2n-2 colors. How many edges would
\nthere be with each color? The average would be (2n-1)(n-1)\/2n-2 – the total number of edges divided by the number of colors.
\n* If the coloring works, than there can’t be more that N-1 edges with the same color,
\nor else there’d be a vertex with the same color for two of its edges: since the number
\nof edges is (2n-1)(n-1), and there are 2n-1 vertices, then if any color is assigned to
\nmore than n-1 edges, then some vertex must have two edges with the same color.
\n* But since the number of edges is (2n-1)(n-1), and the number of colors 2N-2 is less that 2n-1, then the average number of edges per color must be *greater than* n-1, which means that at least one color is assigned to n edges.
\nSince that’s a contradiction, we know that we can’t color K2n-1<\/sub> in less than 2n-1 colors.<\/p>\n","protected":false},"excerpt":{"rendered":"

In addition to doing vertex and face colorings of a graph, you can also do edge colorings. In an edge coloring, no two edges which are incident on the same vertex can share the same color. In general, edge coloring doesn’t get as much attention as vertex coloring or face coloring, but it can be […]<\/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-460","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7q","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/460","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=460"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/460\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=460"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=460"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}