"Can everyone please be seated?" I think we're all used to hearing this question at the beginning of events. You're supposed to react by planting your butt in the nearest available chair. But that's NOT my intended meaning-- stroll around to your heart's content. In fact, my goal today is to instill a completely different response along the lines of, "Thank you for asking! Actually, it depends on the chromatic properties of a certain theoretic graph." Let's take seating you guys in this classroom as an example. Now, I hope you mostly get along, but I'm sure conflicts occasionally arise: "You ate my Ben & Jerry's... did not, did to, did not, did to... Well, cherry garcia is gross anyway." And people in conflict might not want to sit near each other. Let's model this situation with a "conflict graph". The vertices are you guys. And we'll put an edge between every pair of people in conflict. Now let's look at the situation from above. Here's the board, here's me, the table, and the seating area. Let's divide that into a left half and a right half. And let's say that if x and y are people in conflict, then they don't want to even sit in the same half of the room. So then the question "Can everyone be seated?" amount to asking whether we can place each vertex of the graph on either the right side of the classroom or the left in such a way that every edge-- every conflict-- runs across the center line. In other words, no two people in conflict are on the same side. ------------------------------------------------------------------------------- Let's try an example. Suppose the conflict graph looks like this. Now, say we assign each side of the room a color-- the left side will be red and the right side is blue. Now the question is, can we color each vertex red or blue (meaning, assign each person to the left side or the right) so adjacent vertices are different colors (that is, the people in conflict are assigned to opposite sides)? Well, what do you think? Can you find a way? [Yup! That works!] If you can color each vertex red or blue so neighbors are different colors, the graph is said to be "2-colorable" or equivalently "bipartite". The 2-colorable name is obvious and "bipartite" reflects the fact that the vertices in such a graph can be divided into two parts in this way. Can anyone think of a way to make this graph NOT bipartite by adding just one edge? Right! How do you know that's not bipartite? Maybe if I'm really clever I can find a coloring? ------------------------------------------------------------------------------- Now this lecture hall actually has about 5 or 6 different seating sections. So maybe we should only require that enemies sit in different sections. In that case, we'd be interested in graphs that are 5- or 6-colorable. [Write definition.] The "chromatic" number of a graph G is the smallest k for which G is k-colorable. For example, our original conflict graph was 2-colorable. What's the chromatic number with this edge added? Yeah, now it's 3-colorable. It turns out that k-colorable graphs for k > 2 are really difficult to understand. It is easy to figure out whether a graph is 2-colorable or not, but can be really, really hard to figure out whether a graph is, say, 3-colorable. Figuring out whether a graph with 50,000 vertices is 3-colorable or not could take you a lifetime. ------------------------------------------------------------------------------- With that caveat, there are some definite things we can say about coloring. For example, if every vertex has degree at most k, then we can color the graph with k+1 colors. In other words, if no one has more than 3 enemies, then we can definitely seat you all in 4 sections. ------------------------------------------------------------------------------- Now this definition is a little imprecise. I should probably say that by a drawing of a graph, I mean each vertex is associated with a point in the plane, each edge is associated with a simple curve joining its endpoints, and those curves don't intersect. And this leads to a big theoretical issue associated with planar graphs: a lot of stuff about geometry in the plane that seems intuitive actually requires heavy mathematical machinery to prove. The most famous example is the Jordan Curve Theorem. --- So this creates a dilemma: planar graphs are important and come up all the time, but a completely rigorous discussion of the associated geometry is far beyond the scope of this class. So the way out is that when we need a geometric fact that seems obvious, we'll just assume it. But I don't want to conceal this issue. ------------------------------------------------------------------------------- G' is still connectd; any path that previously went through the edge x--y that we removed can be rerouted around the remainder of the cycle. ------------------------------------------------------------------------------- Now we can use Euler's formula =============================================================================== =============================================================================== coloring graphs assigned students to recitations [at least one other example] max degree k => k+1 colorable bipartite graphs bipartite iff no odd cycle =============================================================================== coloring =============================================================================== Thm Graph with max degree <= k is (k+1)-colorable. --- Pf By induction. P(n) = claim holds for n-vertex graphs. -- Base case: 1 vertex => degree 0 and is 1-colorable. [dot] Inductive step: Assume P(n) to prove P(n+1) where n >= 0. Let G be (n+1)-vertex graph with max degree <= k. Remove a vertex v, leaving G' with max degree <= k. Can k-color G' by P(n). Add back v. k neighbors, k+1 colors available. Can color v differently from neighbors. =============================================================================== planar graphs =============================================================================== Puzzle #1 [five quadapi] Can five quadapi all shake hands without crossing arms? ------------------------------------------------------------------------------- Puzzle #2 [Three dogs, three houses.] Find a path from each dog to each house so no two paths intersect? ------------------------------------------------------------------------------- A planar graph can be drawin in the plan so no edges cross. ------------ K_(3,3) K_5 Both: NON-planar, but PLANAR if remove any edge (demonstrate on K_5) ------------------------------------------------------------------------------- planar graph has a planar embedding (drawing): ------------ -------------------------- vertex v -> point p_v in R2 DON'T edge (u, v) -> continuous curve c_(u, v) PANIC o Endpoints of c_(u, v) are p_u and p_v. o c_(u, v) intersects no edge curve or vertex point except at endpoints. ------------------------------------------------------------------------------- Jordan Curve Theorem: simple closed curve has inside and outside [curve, inside-outside] [Up to 1800's, obvious-- axiom. 1887 Jordan: provable. 20 years: proof. Some nasty curves! We'll assume geometric facts we need.] A drawing partitions plane into faces. ----- [example] [Theme in 6.042: cover each topic up to Euler's theorem, b/c Euler has a theorem on EVERY topic.] ------------------------------------------------------------------------------- Euler's Formula --------------- For every drawing of a connected planar graph v - e + f = 2 v = # vertices, e = # edges, f = # faces [cite example above] ------------------------------------------------------------------------------- Pf: By induction on # edges. P(e) = "v - e + f - 2 in every drawing in every drawing of connected e-edge graph" Base case: e = 0 => v = 1 vertices, f = 1 faces 1 - 0 + 1 = 2 ------------------------------------------------------------------------------- Inductive step: Assume P(e) to prove P(e + 1). Take G with v vertices, e + 1 edges, f faces for e >= 0. ===== Case 1: G acyclic => G is tree => v = e + 2 , f = 1 (e + 2) - (e + 1) + 1 = 2 [tree] ------------------------------------------------------------------------------- Case 2: G has cycle. [picture] Remove edge (x, y) on cycle. Gives G'. G' connected, e edges, v vertices, f - 1 faces. By induction v - e + (f - 1) = 2. => v - (e + 1) + f = 2 ------------------------------------------------------------------------------- Polyhedra: [tetrahedron] [cube] [octahedron] Faces are regular n-gons, m edges meet at each corner. ------------------------------------------------------------------------------- Polyhedra -> planar graphs [tetrahedron] [cube] [octahedron] ------------------------------------------------------------------------------- m edges incident to v vertices => mv = 2e n sides on f faces => nf = 2e v - e + f = 2 => (2e/m) - e + (2e/n) = 2 => 1/m + 1/n = 1/2 + 1/e m > 5 => left side <= 1/6 + 1/3 = 1/2 < right 3 <= n, m <= 5 ------------------------------------------------------------------------------- no soln n m v e f n = 4, m = 4 3 3 4 6 4 tetrahedron n = 4, m = 5 ...etc... n = 5, m = 4 n = 5, m = 5 ------------------------------------------------------------------------------- Hall's theorem (6 cards) =============================================================================== Hall's Theorem =============================================================================== Case 2. Some proper subset W of women likes exactly |W| men. Match these women by P(|W|). Consider subset W' of remainder. By MC, W U W' liked at least |W U W'| men W' like at least |W'| men MC still holds, match remainder by P(n - |W|)