Math.dartmouth.edu

1.1.30 Let G be a simple graph with adjacency matrix A and incidence matrix M . Prove that the degree of vi is the ith diagonal entry of A2 and M M T . What do theentries in position (i, j) of A2 and M M T say about G? Proof. Since A is symmetric, the ith diagonal entry of A is the dot product square of thevector In general, the dot product square of a vector is the sum of the squares of the entries in thevector. Since all of the entries of v are 1 or 0, v · v is just the sum of the entries of v, whichis the degree of vi. The ith diagonal entry of M M T is the dot product square of Again, this is just the sum of the entries in w(i), which is also the degree of vi.
In A2, the (i, j) entry is the dot-product v(i) · v(j), which will again be the sum of 1’s and 0’s: a 1 occurs in the kth summand if vi and vj share vk as a neighbor. So (i, j) entry is thenumber of neighbors vi and vj have in common!(Fun fact: In general, the (i, j) entry of Ak will be the number of length k walks from vi Similarly, the (i, j) entry of M M T is the dot product w(i) · w(j), which will again be the sum of 1’s and 0’s: a 1 occurs in the kth summand if vi and vj share ek as an edge. So (i, j)entry is the number of edges joining vi to vj.
1.2.1 Determine whether the statements below are true or false.
(a) Every disconnected graph has an isolated vertex.
is disconnected and has no isolated vertex.
(b) A graph is connected if and only if some vertex is connected to all other True. IF the graph is connected, then by definition, any vertex is connected to everyother vertex in G. On the other hand, if there is a vertex that is connected to every othervertex in G, then by transitivity (of the connection relation), every other pair of verticesis also connected (it P is a u, v-path and P is a v, w-path, then P followed by P is au, w-walk, which contains a u, w-path).
(c) The edge set of every closed trail can be partitioned into edge sets of cycles.
True. This is certainly true for a closed trail which is a single vertex or any trail whichis itself a cycle. If a closed trail T is not a cycle, then either (1) the first/last vertex isrepeated more that just the twice, or (2) there is some other vertex which is repeated;call this special vertex a. Decompose the trail T into T1, the trail which walks to the first occurrence of a and skips everything between then and the second occurence of a and then completes the rest of T , and T2, which starts at the first occurrence of a and walks to the second occurrence of a.
Both T1 and T2 are closed trails of shorter length than T . Strongly induct on the lengthof T .
(d) If a maximal trail in a graph is not closed, then its endpoints have odd degree.
True. If a trail is not closed, then for each endpoint, the number of edges in the trailwhich are incident to that endpoint must be odd. If a trail is maximal, then there areno edges incident to the endpoint(s) which are not already in the trail; so the number ofedges in the trail which are incident to each endpoint is equal to the degree of that vertex.
1.2.4 Let G be a loopless graph. For v ∈ V (G) and e ∈ E(G), describe the adjacency and incidence matrics of G − v and G − e in terms of the corresponding matrices for G.
G − e: Suppose the endpoints of e are u and v. The adjacency matrix is the same as that of G, except in the (u, v) and the (v, u) entries, which are each reduced by exactly 1.
The incidence matrix has one fewer columns than I(G) (the one corresponding to e), and isotherwise unchanged.
G − v: The adjacency matrix is one dimension smaller, and is achieved by deleting the row and column of A(G) corresponding to v. The incidence matrix has one fewer row anddegree(v) fewer columns and is achieved by deleting the row corresponding to v and thecolumns corresponding to all incident edges to v.
1.2.12 Convert the proof given in item 1.2.32 to a procedure for finding an Eulerian Start by trying to draw an Eulerian trail (recording the order of the edges and vertices).
If you get stuck in one direction, try to extend the the other end (adding edges and verticesin revers order to the beginning). When you run out of room, you must have a closed trailby Lemma 1.2.31. Since it’s closed, think of it as a circuit C, which you can start at any ofits vertices.
If you missed an edge e, find a path from e to your circuit (which doesn’t intersect unnec- essarily with C). Then start a new trail which starts at a far endpoint of e, follows the pathto C, and then continues around C. If this new trail is not closed, you can close it again byLemma 1.2.31. Iterate until there are no edges left.
Closing it off (in reverse): E–B–F–E–C New Trail: C–E–F–B–E–D–C–F–A–B–C 1.2.15 Let W be a closed walk of length at least 1 that does not contain a cycle. Prove that some edge of W repeats immediately (once in each direction).
Proof. (By strong induction)Let (W ) denote the length of the walk.
Suppose (W ) = 1. If W is closed, then it must be a loop (a cycle of length 1), whichcontradicts the hypothesis. If (W ) = 2 and W is closed, then W is one of the following: pro The latter has a cycle, so it can only be the first, in which the edge e immediately repeats.
Now assume that any closed walk of length k < n which does not contain a cycle has an edge which immediately repeats. Any closed walk with only one repeated vertex (the first)is itself a cycle, so if W = v0, e1, v1, . . . , e v does not contain a cycle, then it must haveanother vertex w which is repeated. Now consider the subwalk U of W which starts at thefirst occurrence of w, continues on W until the second occurrence of w (like T2 in 1.2.1 (c)).
This is a closed walk of length less than (W ), and since W does not have a cycle, neither doesthis subwalk. So, by the induction hypothesis, this subwalk has an edge which immediatelyrepeats. Since consecutive edges of this subwalk also occur consecutively in W , that meansthat there is an edge of W immediately repeats.
1.2.18 Let G be the graph whose vertex set is the set of k-tuples with elements in {0, 1}.
with x adjacent to y if x and y differ in exactly two positions. Determine thenumber of components of G.
Answer: In general, there will be two connected components: (a) one containing all points with an odd number of 1’s, and (b) one containing all points with an even number of 1’s.
A. If two points do not share the same parity of 1’s, then they’re not in thesame component. This can be seen by observing that an edge will only connect twovertices if those vertices have the same parity of 1’s. Therefore, there is no walk (andtherefore no path) in G which contains vertices of both parity’s.
B. Any two points with the same parity of 1’s are in the same component.
We’ll apply transitivity and show that every vertex is connected to one of two specialvertices. Even: you can get to any point with an even number of 1’s from the vertexwith all 0’s by following edges which changes the necessary 0’s to 1’s two at a time. Odd:similarly, you can get to any point with an odd number of 1’s from the vertex with 1in the first place followed by all 0’s as follows: if the desired point has a 1 in the firstcoordinate, then change 0’s to 1’s as needed in pairs; if it doesn’t then switch the 1 to a0 at the same time as switching a desired 0 to a 1, and then switch 0’s to 1’s as needed inpairs. For example, (1,0,0,0,0,0,0,0) is connected to (0,0,1,0,1,1,1,1) by the following path: 1.2.38 Prove that every n-vertex graph with at least n edges contains a cycle.
Proof. If n = 1, and G has one vertex and at least one edge, then it has at least one loop,which is a cycle.
Now suppose n > 1 and G has n vertices and at least n edges. Either (a) every vertex in G has degree at least 2, in which case Proposition 1.2.28 implies G (b) G has a vertex v of degree 1 or 0. Then G − v has n − 1 vertices and at least n − 1 edges (we deleted at most 1 edge in removing v). By strong induction, G − v (andtherefore G) has a cycle.
1.2.42 Let G be a connected simple graph not having P4 or C4 as an induced graph.
Prove that G has a vertex adjacent to all other vertices.
Proof. Since G is connected, any two vertices are connected by a path. Consider two verticesu and v, and pick a minimal u, v-path P = u, e1, v1, . . . , v −1, e , v. Since P is minimal, notwo vi, vj with i = j ± 1 can be neighbors. So G[V (P )] ∼ ≤ 2, and any pair of vertices in G must either be adjacent, or mutually adjacent to at least one vertex.
Now, either G is a complete graph (in which case every vertex is connected to every other vertex), or there are two non-adjacent vertices u and v. We’ll show that any two such verticeshave a common neighbor which is adjacent to all other vertices in G.
Choose a minimal u, v-path, and call the intermediate vertex w. Pick any other vertex x in V (G). Since any minimal path in G connecting two vertices must be of length at most 2,and since G is connected, x is at most 2 away from u, v, and w. If x is not adjacent to w,then G would have one of the following as an induced subgraph (where the dashed edges areunknown): III. x is adjacent to u and v, but not to w.
Therefore, x (any other vertex in G) is adjacent to w.
1.3.9 In a league with two divisions of 13 teams each, determine whether it is possible to schedule a season with each team playing 9 games against teams within itsdivision and four games against teams in the other division.
Answer: Formulating this as a graph theory problem, we need a 26-vertex graph whichdecomposes into a 4-regular bipartite graph with partites X and Y both of order 13, and two9-regular graphs of order 13 (one on each partite of X and Y ). Unfortunately, the latter isn’tpossible because a graph cannot have an odd number odd-degree vertices! It is, however, possible to schedule the four games each across the divisions: Call the teams in division X x1, x2, . . . , x13, and the teams in division Y y1, y2, . . . , y13. For team xi, schedulegames with 1.3.22 Let G be a nonbipartite triangle-free simple graph with n vertices and minimum be the minimum length of an odd cycle in G.
in G. Prove that every vertex not in V (C) has at most two neighbors in V (C).
Suppose x ∈ V (G) − V (C) has three neighbors in V (C). Then those neighbors partitionC into three pieces. Since is odd, at least one of those parts has odd length. And since there are no triangles in G, that part has length at most x to one of the endpoints of that part, along that part, and then back to x, you’ve builtan odd cycle of length less than , a contradiction.
(b) By counting the edges joining V (C) and V (G) − V (C) in two ways, prove that Since δ(G) = k, the edges coming out of V (C) is at least k − 2 (the sum of the degreesminus the edges contributing to C, which were all double-counted). On the other hand,the number of edges coming into V (C) is at most (|V (G)| − |V (C)|) ∗ 2 = (n − ) ∗ 2. So k − 2 ≤ (n − ) ∗ 2 =⇒ k ≤ 2n =⇒ k /2 ≤ n.
(c) When k is even, prove that the inequality of part (b) is best possible.
> 3 odd. Then the criteria above are satisfied by the graph G with V (G) = {(a, b) | 1 ≤ a ≤ k/2, 1 ≤ b ≤ } and E(G) = {(a, b) − (c, d) | b = d ± 1 (mod )}(see the example below). For this graph, n = (k/2) ∗ .
Proof. (1) Any cycle which has an even number of edges (a, )–(b, 1) must be of evenlength (e.g. a cycle with no such edge will have the property that every second coordinatewhich appears must appear an even number of times). So the shortest odd cycle is oflength .
(2) Every vertex has degree k since (a,b) will connect to (c, b + 1 (mod )) and (c, b − 1(mod )) for c = 1, . . . , k. .
(3) G is not bipartite since it has an odd cycle, and has no triangles by (1).

Source: http://www.math.dartmouth.edu/~m38s12/solutions/HW2.pdf