Connected Graphs

1 Connected Graphs Definition 1.1. Let G = (V, E) be a graph and let x, y ∈ V . There is a path from x to y if there is a sequence x = x1 , x2 , . . . , xn = y such that for every i < n, (xi , xi+1 ) is an edge in E. A path is a circuit if x = y. a b For example, in the graph: c d e some paths from a to d include: • a, b, d, • a, c, d, • a, b, c, d, • a, b, c, b, d, • a, b, c, a, b, d. On the other hand, there are no paths from a to e. There is a path from e to e: the path consisting only of e, with n = 1, so there’s only one step in the path. Definition 1.2. A graph is connected if for all vertices x, y, there is a path from x to y. We say y is reachable from x if there is a path from x to y. x is always reachable from itself, if y is reachable from x then x is reachable from y (just reverse the path) and if y is reachable from x and z is reachable from y then z is reachable from x (use one path after the other). A graph can be partitioned into pieces each of which is connected. Each piece is called a component. For example, the graph above has two components— a, b, c, d is one and e is the other. a c e d This graph b has three components: a, b is one, c, d is a second, and e is a third. An observation that will serve us well: each component is an induced subgraph of the original graph, and each vertex has the same degree within its component as within the whole graph. Our first actually interesting theorem: Theorem 1.3. In any graph, the sum of the degrees is twice the number of edges. In symbols X deg(v) = 2|E|. v∈V 1 This is basically P obvious: each edge is adjacent to two vertices, so each edge contributes 2 to v∈V deg(v). Corollary 1.4. The number of vertices of odd degree is even. This is obvious, but it means we can rule out certain graphs as not existing because it’s obvious. For example: is it possible to have a group of 7 people each of whom knows exactly 3 others? No: we could draw a graph where the vertices are people with edges for pairs who know each other. Together, these ideas will let us solve the Mountain Climbers Puzzle. Imagine that we have a mountain with various peaks and valleys. Two climbers start at the opposite ends, assumed to have the same altitude, and they intend to meet at the summit. The rule is they must, at all times, have the same altitude. We are assuming they start at the lowest point and are aiming to meet at the highest point. The question is whether this is always possible? M t s d x w f a z For example, one climber starts at a and one at z. They must both climb until the one on the right reaches x. At this point, in order to go on, the one on the right must go down to w, so the climber on the left must start going back down, towards the left, until the climber on the right reaches w, at which point they can both climb up again...until the left climber reaches d, at which point the right climber, who has not yet reached t, must go down. We label some additional points on the graph: all points in the middle of a slope which have the same height as a peak or valley on the other side of M : M t i s u d h g c e x b w f a y z A general idea: we will make a graph whose vertices are “interesting valid positions”. In this case, the interesting valid positions are pairs of positions, one for the left climber and one for the right climber, such that: • The left climber is to the left of (or at) M and the right climber is to the right of (or at) M , • The climbers are at the same height, • At least one climber is at a peak or valley. 2 For instance, (a, z), (m, m), (b, w), and (d, s) are all vertices. (b, y) is not a vertex; it’s a valid position, but it’s not interesting because we don’t have any decision to consider there. We draw an edge between two vertices if it is possible to move between those positions in one step—if we get from one to the next by both climbers moving up or both moving down for the whole way. For instance, (a, z) has an edge to (x, c) (in fact, its only one). Our graph is (M,M) (i,t) (d,u) (d,s) (h,s) (c,x) (e,x) (g,x) (b,w) (f,w) (f,y) (a,z) From this graph it’s very easy to read off the solution. Furthermore, it gives us a clue how to prove that there’s always a solution. The idea is to examine the degrees of the vertices: we claim that (a, z) and (M, M ) have degree 1, and every other vertex has degree 0,2, or 4. To see that (a, z) always has degree 1, observe that the only option is for both climbers to begin going up and in until they reach the first peak on one side; this is a single node. Similarly, from (M, M ), the only option is to go down and out until they reach the first valley on one side. Consider some other node; call it (p, q). At least one of p and q is a peak or a valley. Suppose both p and q are valleys, like (f, w); then we have four options—we go up from both nodes, and can choose left or right at each. If both p and q are peaks, the same. If one is a peak and the other is a valley, like (d, s), the degree is 0—one node demands going up, the other demands going down, and this is impossible. (Fortunately, we can’t reach such a node either.) If only one is a peak or valley, and the other is in the middle, like (b, w), then we only have two options—we go up from the valley left or right, and go up in the only possible way from the middle. Again a peak is similar. So the only nodes with odd degree are (a, z) and (M, M ). Consider the connected component containing (a, z). Since it contains (a, z), which has degree 1, it must contain another vertex of odd degree, and the only possibility is (M, M ). So (M, M ) is reachable from (a, z). In case this seems completely artificial, this kind of problem actually comes up in robotics: if you want to get a robot to maneuver a chair through a doorway, it has to consider similar issues. 3 2 Planar Graphs Definition 2.1. A graph is planar if there is any way to draw it on a chalkboard so the edges do not cross. It’s very important to understand that planarity is about the possibility of drawing the graph this way, not whether we actually do so. For instance a b c is a planar graph because we could redraw it so the lines don’t cross. An idea we’ll return to later is that planar graphs are related to maps: if I take a map—a bunch of countries with borders—and turn each country into a vertex and draw an edge between adjacent countries then the resulting graph is planar. (Assuming that the countries are contiguous.) To see this, imagine placing the vertex in the interior of each country and drawing each line to cross the relevant border. Important idea: if a graph is planar, all its subgraphs are planar. Conversely, if a graph is non-planar, any graph containing it is non-planar. Therefore a way to show that a graph is non-planar is to identify a subgraph which we already know to be non-planar. But how can we show, for certain, that any graph is non-planar? Consider any drawing of a planar graph. Notice that it divides the plane into a bunch of regions, separated by lines. (It’s important to include the “outside” of the graph as one of the regions.) d 4