Counting by DegreesSex in AmericaHandshaking LemmaConnectednessPaths and Simple CyclesConnected ComponentsHow Well Connected?Connection by Simple PathThe Minimum Number of Edges in a Connected GraphTreesTree PropertiesSpanning TreesColoring Graphsk-ColoringBipartite GraphsPlanar GraphsEuler's FormulaNumber of Edges versus VerticesClassifying PolyhedraHall's Marriage TheoremA Formal StatementAppendix: Drawing Planar GraphsMassachusetts Institute of Technology Course Notes, Week 56.042J/18.062J, Fall ’05: Mathematics for Computer Science October 3Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised October 17, 2005, 468 minutesGraphsAs in Week 4 Notes, we’ll refer to undirected graphs simply as “graphs.”1 Counting by Degrees1.1 Sex in AmericaA 1994 University of Chicago study entitled The Social Organization of Sexuality found that onaverage men have 74% more opposite-gender partners than women, confirming a view that menare more promiscuous. But whoever reported this finding was lying or confused! We’ll show youhow to use the properties of vertex degrees in a graph to prove this.Let’s recast opposite-gender partnering in graph theoretic terms. Let G be a graph where the setof vertices V consists of everyone in America. Now each vertex either represents either a male ora female, so we can partition V into two subsets: M , which contains all the male vertices, and F ,which contains all the female vertices. Let’s draw all the M vertices on the left and the F verticeson the right:M FNow, without getting into a lot of specifics, sometimes an edge appears between an M vertex and aF vertex:M FCopyright © 2005, Prof. Abert R. Meyer. All rights reserved.2 Course Notes, Week 5: GraphsSince we’re only considering opposite-gender relationships, every edge connects an M vertex onthe left to a F vertex on the right. So the sum of the degrees of the M vertices equals the numberof edges and so does the sum of the degrees of the F vertices. So these sums are equal:Xx∈Mdeg(x) =Xy∈Wdeg(y)Now suppose we divide both sides of this equation by the product of the sizes of the two sets,|M| · |F |:Px∈Mdeg(x)|M|·1|F |=Py∈Wdeg(y)|F |·1|M|The terms above in parentheses are the average degree of an M vertex and the average degree of a Fvertex. So we know:Avg. deg in M|F |=Avg. deg in F|M|Avg. deg in M =|F ||M|· Avg. deg in FIn other words, we’ve proved that the average number of opposite-gender partners of males inthe population compared to those of females is determined solely by the relative number of malesand females in the population.Now the Census Bureau reports that there are slightly more females than males in America; inparticular |F | / |M| is about 1.035. So we know that on average, males have 3.5% more opposite-gender partners than females, and this tells us nothing about any sex’s predilection toward promis-cuity. We can only wonder where the University of Chicago researchers got their 74% difference.1.2 Handshaking LemmaThe previous argument hinged on the connection between a sum of degrees and the numberedges. There is a simple connection between these in any graph:Theorem 1.1. The sum of the degrees of the vertices in a graph equals twice the number of edges.Proof. Every edge contributes two to the sum of the degrees, one for each of its endpoints.Theorem 1.1 is sometimes called the Handshake Theorem: if we total up the number of peopleeach person at a party shakes hands with, the total will be twice the number of handshakes thatoccurred.2 Connectedness2.1 Paths and Simple CyclesPaths in graphs are defined in pretty much that same way as for digraphs, but they are going tobe particularly important, so let’s define them precisely.Course Notes, Week 5: Graphs 3Definition 2.1. Let G be a graph with vertices, V , and edges, E. A path in G is a sequence ofverticesv0, . . . , vkwith k ≥ 0 such that vi—vi+1is an edge in E for 0 ≤ i < k. The path is simple iff all the vi’s aredifferent, that is, vi= vjonly if i = j.The path is said to start at v0, to end at vk, and length of the path is defined to be k. An edge, e, istraversed n times by the path if there are n different values of i such that edge vi—vi+1is e.For example, the graph in Figure 2.1 has a length 6 simple path A,B,C,D,E,F,G. This is the longestsimple path in the graph.ABCD EFGHFigure 1: A graph with 3 simple cycles.Notice that the length of a path is the total number of times it traverses edges, which is one lessthan its length as a sequence of vertices. The length 6 path A,B,C,D,E,F,G is actually a sequence ofseven vertices.Cycles are paths that begin and end with the same vertex, same as for digraphs. Simple cycles willbe cycles that don’t cross themselves. For example, the graph in Figure 2.1 has three simple cyclesB,H,E,C,B and C,D,E,C and B,C,D,E,H,BA simple cycle is can be described by any of the paths that go around it. For example, the pathB,H,E,C,B describes the cycle as beginning and going clockwise around to end at B, while the pathE,H,B,C,E, describes the same cycle as beginning and ending at E going counterclockwise.To capture this precisely, we’ll define a simple cycle to be a subgraph isomorphic to the simplecycle graph, Cn. A subgraph is obtained by restricting a graph to a subset of its vertices and thenpossibly deleting some additional edges. Formally:Definition 2.2. A subgraph, G0, of a graph, G, is a graph whose vertices, V0, are a nonempty subsetof the vertices of G and whose edges are a subset of the edges of G.Notice that since a subgraph is itself a graph, the endpoints of every edge of G0must be verticesin V0.Definition 2.3. For n ≥ 3, let Cnbe the graph with vertices 1, . . . , n and edges1—2, 2—3, . . . , (n − 1)—n, n—1.4 Course Notes, Week 5: GraphsA graph, C, is a simple cycle of length n iff it is isomorphic to Cnfor some n ≥ 3. A simple cycle of agraph, G, is a subgraph of G that is a simple cycle.If we describe a simple cycle with a path around it, then the length of a cycle is the number of timesthe path traverses an edge which is the same as the number of distinct vertices on the path. Forexample, the cycle with 5 vertices described by the path B,C,D,E,H,B has length 5.2.2 Connected ComponentsDefinition 2.4. Two vertices in a graph are said to be connected if there is a path that begins at oneand ends at the other.Now if there is a path from vertex u to vertex v, then v is connected to u by the reverse path, soconnectedness is a
View Full Document
Unlocking...