3.1. Method 1: Let n be the number of vertices in the tree, and use induction on n.

Base  case:  For n = 1, there is just one vertex, v.  Then A = {v}, B = 0 gives the bipartition; there are no edges, so there are no edges between vertices in A or between vertices in B .

Induction step:  For n > 2, the induction hypothesis is all trees with n · 1 vertices are bipartite.

Let T be any tree on n vertices. Let z be any leaf of T. Then T/ = T ·{z} is a tree with n · 1 vertices. By the induction hypothesis, T/  has a bipartition into sets of vertices A/  and B/ .

Let e = {v, z} be the unique edge on z in T. The vertex v is either in A/ or in B/  (but not both). If v e A/ , then set A = A/  and B = B/ u{z}; while if v e B/ , then set A = A/ u{z} and B = B/ .

Then A, B is a bipartition of the vertices of T.

Method 2: Pick any vertex as the root, r.  Compute the depths of all vertices with respect to that root.  Let A be the set of all vertices whose depths are even, and B be the set of all vertices whose depths are odd. In a tree, each edge connects vertices whose depths differ by 1, so each edge connects one vertex with even depth and one vertex with odd depth; that is, one from A with one from B . So the graph is bipartite.

Method 3: The textbook (and slides) show that a graph is bipartite if and only if it does not contain any odd length cycles.  The proof of that is related to  “Method 2” above.  Since a tree doesn’t have any cycles at all, it doesn’t have any odd length cycles, so by this result, it’s bipartite.

3.2. Left graph:  Doing a traversal and marking alternate vertices A/B gives a split into A = {2, 3, 4, 5, 6, 7, 8} and B = {9, 10, 11, 12, 13, 14, 15, 1}. All edges have one vertex in A and one in B . It’s also valid to switch which one is called A vs. B , or may name them differently.

Right graph: There’s a length 3 cycle near the top: 3, 4, 24, 3. A bipartite graph can’t have an odd-length cycle, so it’s not bipartite. There may also be other ways to show it’s not bipartite.

Common question: As a bipartite graph, every edge must have one vertex A and the other in B.  Whereas a complete  bipartite graph has all possible edges {a, b} where a e A and b e B.  We are just saying that the left graph is a bipartite graph, not that it is a complete bipartite graph. For example, 4 e A and 1 e B do not form an edge.

3.3(a).

DFS                                BFS

Parts (c,d) refer to the original graph, NOT to the trees constructed in (a).  So there should only be one answer for (c) and one answer for (d), each based on the original graph; not two answers for (c) and two for (d) based on the DFS and BFS trees.

2

(c) There is no vertex within 1 of all others, but there are some vertices within 2 of all others: v2 ,v3 ,v4 ,v5 ,v7. So the radius is      .

(d) The  maximum  distance  in  the  graph  is  .   It’s  achieved  by  d(v1 ,v8 )  =  d(v1 ,v9 )  = d(v6 ,v8 ) = d(v6 ,v9 ) = 3.

Common mistakes:

(b) Giving DFS height 6 or BFS height 4. It appears people counted layers. But the root is at depth 0, not 1; its children are at depth 1, not 2; etc.  The length of a path from the root to another vertex is measured in edges, not in vertices (which would give a count 1 higher).

(d) Saying the diameter is 8. It appears people are looking for the longest possible path in the graph.  But that’s not how diameter is defined.  For each pair of vertices, you need to find the SHORTEST path between them to get their distance; and then you need to take the BIGGEST of these distances. So although there is a longest path v1 · v4 · v5 · v6 · v7 · v2 · v3 · v9 · v8  of length 8, the distance from v1 to v8  is not 8! The shortest path from v1 to v8  is v1 · v4 · v3 · v8 , so d(v1 ,v8 ) = 3.

3.8. Call the graph G. Pick any vertex as v1 . Use either depth first search or breadth first search to form a spanning tree, T, with v1  as the source / root. Number the other nodes v2 ,...,vn  using time stamps like in the class slides (equivalently, number them in the order they are discovered). For every vertex vi  (except v1 ), its parent vj  in T has a smaller time stamp (that is, j < i).  The spanning tree T is a subgraph of G, so vjvi  is also an edge in G.  So we have shown that if i  1, then vi  has at least one neighbor vj  in G with j < i.

3.9. Let v1 ...vr be a longest path in the graph. If any of the incoming edges to v1 are from vertices besides v2 ,...,vr, then we could have extended the path by adding another vertex before v1. But that would contradict that this is a longest path in the graph. Thus, the incoming neighbors of v1 are a subset of {v2 ,...,vr}. This is a set of size r · 1.

Vertex v1  has d- (v)  >  k  (since the minimum indegree is at least k), and this is a subset of {v2 ,...,vr} (size r · 1), so k < r · 1. Thus, r > k +1.

Pick the largest i in 2, 3,...,r such that there is an edge (vi,v1 ). Then i > k + 1 (since at least k · 1 vertices in v2 ,...,vi-1  have edges to v1 ).

Then v1 ,v2 ,...,vi,v1  is a directed cycle of length at least k +1.

3.10. Method 1: Suppose G has n vertices, m edges, and k components, with n, m, k > 1. Form a spanning tree of each connected component, and put all the trees together to get a spanning forest F of G. Then F is a subgraph of G with n vertices and n · k edges, so m > n · k .

Let  S  =  E (G) \ E (F);  this is the set of edges of G that were removed to form F .   Then ISI = m · (n · k) = m · n + k .

For each e = {u, v} e S , the graph F u{e} is a subgraph of G and has a cycle through e:

● There is a unique path in F between u and v (since they are in the same tree); adding e to F closes that path into a cycle.

● Each e e S is in just one cycle constructed that way, so these cycles differ for each e.

● Thus, we have constructed m · n + k cycles in G.

There may be more cycles in G besides the ones we constructed (namely, cycles that include two or more edges from S), so the actual number of cycles in G is > m · n + k > m · n +1.

Method 2:  Define n, m, k the same way as in Method 1.  This proof is similar, but we will induct on m. As shown above, m > n · k, so the base case is m = n · k, not m = 0 or 1.

Base case: G has m = n · k edges: Then G is a forest, so it has no cycles. Computing m · n +1 gives (n · k) · n +1 = 1 · k < 0, so indeed, 0 cycles is > m · n +1.

Induction step: For m > n · k, assume the statement holds for all graphs with n vertices, k components, and m · 1 edges.

Let F be a spanning forest of G; then F has n · k edges.

Let S = E (G) \ E(F); then ISI = m · (n · k) > 0 (since we’re in the case m > n · k), so S is nonempty.

Pick any e = {u, v} e S (that is, any edge of G that’s not in F).

Let G/ = G ·{e}. Then G/  has n vertices, k components, and m · 1 edges, so by the induction hypothesis, G/  has at least (m · 1) · n +1 = m · n cycles.

Note that G has all the cycles that G/  has. But additionally, u and v are in the same tree of F and have a unique path between them in that tree. Adding e to that path forms a cycle in G. This cycle was not present in G/  since e isn’t in G/ , so we’ve added at least one more cycle. There may also be other cycles in G that go through e (such cycles would have to use at least two edges of S instead of exactly one), so it’s “at least one more cycle” rather than “exactly one more cycle.” Thus, G has at least (m · n) + 1 cycles.

Note: The homework sheet said you could assume G is connected; that’s just to make a simpler version of the problem, but as shown above, the statement is also true for disconnected graphs. If you only consider connected graphs, then k = 1; you can use a spanning tree T of the graph instead of a forest F with k trees; and m · n + k = m · n + 1. In Method 2, the base case would become m = n · k = n · 1.

H-301.

(a) The odd degree vertices are a, c, d, g. They can be paired up as ac + dg , ad +cg, or ag + cd.

For ac + dg: The smallest weight path from a to c is a, g, c (weight 10 + 10 = 20).

The smallest weight path from d to g is the edge ag , weight 5.

The total for this option is 20 + 5 = 25.

For ad + cg: The smallest weight path from a to d is a, e, d (weight 4 + 8 = 12). The smallest weight path from c to g is the edge connecting them, weight 10.           The total for this option is 12 + 10 = 22.

For ag + cd: The smallest weight path from a to g is a, g , of weight 10.

The smallest weight path from c to d is c, g, d of weight 10+5 = 15 (not the edge connecting them, which is bigger, 20).

The total for this option is 10 + 15 = 25.

The best of the three options is ad+cg. So add second edges for ae, ed, cg. Then find any Eulerian tour starting at d. One solution (there are many more) is d, e, a, b, c, d, e, a, g, c, g, d.

The cost of any solution is 2(4 +8+10)+10+30+5+5+20 =          .

Common mistakes:

– Finding a path but not a least weight path. For a least weight path from a to d, using a, g, d (weight 10 + 5 = 15) instead of a, e, d (weight 4 + 8 = 12).

– Giving a tour that does not visit every edge. In some cases, it appears people thought the goal was just to visit every vertex.

There are other ways to write the same cycle by starting at any of the five vertices, and following it in either of the two directions.

There are 10 edges altogether in the graph, and this uses five of the six smallest weights (2, 4, 6, 8, 10, 12). The only way to get 5 of the 10 edges to add up to a smaller value would be to replace the 8, 10, or 12 by 6, provided that formed a Hamiltonian cycle.  However,