MTH 482
Old Homework

1. Show that any maximal planar graph with n ≥ 4 vertices has 3 ≤ κ(G) ≤ κ'(G) ≤ 5. Hint: Any planar graph has a vertex of degree ≤ 5.
2. Do there exist maximal planar graphs G having each of the possibilities (κ(G), κ'(G)) = (3,3), (3,4), (3,5), (4,4), (4,5), (5,5)?

1. List all 2⁴ = 16 edge-cuts (S,T), and for each compute its capacity cap(S,T) as well as the flow volume flow_f(S, T), which should be the constant flow(f). Is flow(f) equal to the minimal capacity of a cut? If not, then f is not a maximal flow for this network?
2. Apply the Augmenting Algorithm starting with f₀ = f . Draw the graph G' . Find an augmenting path P in G' from s to t, and compute the augmented flow f₁ = f '. Notice how the algorithm corrected a "mistake" in f to give a better f' .
3. Repeat the algorithm if necessary, and in the end produce a flow f_n which is demonstrated to be maximal by an edge cut (S,T) with flow(f_n) = cap(S,T) .

1. Let us generalize our notion of a network to allow multiple sources s₁, s₂,... and sinks t₁, t₂.... State an appropriate MF/MC Theorem for this situation. (Modify the definition of a flow and an edge-cut.) Prove your statement by reducing it to the original MF/MC.
2. A different modification to the original MF/MC: instead of specifying edge-capacity, specify vertex-capacity: at each vertex v ≠ s,t, we impose a bound cap(v) on the outflow volume (= inflow volume) of a flow f at v. Again prove the appropriate MF/MC Theorem by reducing it to the original theorem.
3. Formulate and prove the most general version of MF/MC you can.
4. What generalizations of Menger's Theorem correspond to the above generalizations of MF/MC?

1. Edge Menger Theorem. We let a simple graph G with marked vertices x,y correspond to the network (G, x, y, c), where each edge xy ∈ G corresponds to a pair of edges (x,y) and (y,x) ∈ G ; x is the source, y the sink; and the capacity function c(x,y) = 1 for all edges. Given a family of edge-disjoint paths ℘ = {P₁,...,P_k}, write the corresponding flow f on G with flow(f) = k. Show that this f has no circulation.   This flow might have circulation, i.e. a directed cycle C in G with f(x,y) > 0 for every edge of C. (Thanks to Ian Desilva for the correction.)
2. Let f be an arbitary flow on the above network (G, x, y, c). Since the net flow at any vertex v is zero, there must be as many edges with inflow 1 as edges with outflow 1. Make an arbitrary matching of these in-edges with the out-edges at each vertex. Show that this makes f correspond to an collection of edge-disjoint paths and cycles in G, and the number of paths is the volume of the flow. Show further that a maximal-volume flow corresponds to a maximal path family, and vice-versa.
3. Show that a minimal edge-cut of the graph G (a set of edges which disconnects G) corresponds to the edges E(S,T) between the parts of a minimum-capacity cut (S,T) of G.
4. Vertex Menger Theorem. We let a simple graph G with marked vertices x,y, correspond to the new network G_± . For each vertex v ∈ G with v ≠ x,y we define two vertices v_- , v₊ ∈ G_± , and an edge (v_-,v₊) ∈ G_± with capacity c = 1. We do not split x and y, making these be the source and sink vertices of G_± . For each edge uv ∈ G, we define two edges(u₊,v_-) , (v₊,u_-) ∈ G_± with capacity c = ∞. Show the same analogies as above between vertex-independent path families in G and flows in G_± ; and between minimal vertex-cuts of G and minimal-capacity cuts (S,T) in G_± .

1. Suppose there are senators A,B,C,D,E,F, from whom are chosen committee 1 (members A,B,C,D), committee 2 (members A,E,F), committee 3 (members D,E,F) and committee 4 (only A). Draw a bipartite graph which reflects this situation (with vertices corresponding to committees and senators). We wish to choose an executive council with one member representing each committee, but no member representing more than one committee. Show that a matching of committees to their member senators corresponds to a choice of executive council. (HHM p 60)
2. Consider a family of sets A₁ ,..., A_m . We wish to choose a set of distinct representatitives a₁ ∈ A₁, ... , a_m ∈ A_m.
   Claim:   If for every I ⊂ {1,...,m}, we have: |∪_i∈I A_i| ≥ |I| . Then the family {A₁ ,..., Am} does possess a set of distinct representatives. Prove this using the Hall Theorem. (HHM p. 65; FCM p. 78)

• vertices A ∪ B ∪ {s,t} with source s, sink t
• edges {(a,b) for ab ∈ E} ∪ {(s,a) for a ∈ A} ∪ {(b,t) for b ∈ B} ;
• all edge capacities c = 1.

1. The Platonic graphs.
   Answer: For G a d-regular Platonic graph , κ(G) = d. Thus for k ≤ d, the whole G is a k-block, while for k > d , there are no k-blocks.
2. The hypercube graph defined in Test 1.
   Answer: This G is 4-regular and 4-connected, and the same analysis holds as above.
3. The graph whose vertices are V = {a,b,c,d,a',b',c',d'}, with K₄ subgraphs on {a,b,c,d} and on {a',b',c',d'}, and one extra edge aa'.
   Answer: 2- and 3-blocks {a,b,c,d} and {a',b',c',d'}, and no k-blocks for k > 3.
4. Same, but with extra edges aa', bb'.
   Answer: 2-block G, 3-blocks {a,b,c,d} and {a',b',c',d'}, and no k-blocks for k > 3.
5. Same, but with extra edges aa', bb', cc'.
   Answer: 1- 2- and 3-block G, and no k-blocks for k > 3.
6. The wheel graph W_n+1 consisting of a n-cycle C and an extra vertex adjacent to every vertex of C.
   Answer: This graph is 3-regular and 3-connected, so the analysis is same as (a) & (b).

1. As in part (ii) of the algorithm, let G = G₁ &cup G₂ such that G₁ &cap G₂ = {x,y} is a minimal separting set. Suppose TK₅ or TK_3,3 ⊂ G₁ + xy . Then construct TK₅ or TK_3,3 ⊂ G.
   Answer: If G₁ has a TK₅ containing the edge xy, let x',y' ∈ G₂ be neighbors of x and y respectively, lying in a single component of G₂ - {x,y}. (Such x', y' exist because {x,y} is a minimal separating set of G.)  Let P be a path from x' to y' in G₂ - {x,y}. Then replacing the edge xy in TK₅ ⊂ G₁ by the path xx'Py'y gives a TK₅ in G. Same applies for TK_3,3 .
2. As in part (iii) of the algorithm, suppose G' = G/xy has a TK₅ or TK_3,3 . Then construct TK₅ or TK_3,3 ⊂ G. Hint: Expanding TK₅ ⊂ G' might produce TK_3,3 ⊂ G.
   Answer: If we have a TK₅ subgraph H' ⊂ G', and we expand any vertex v ∈ H' into two new vertices x,y to get a new graph H, at least one will have degree ≤ 2, so that H is still a TK_3,3 . The same holds for TK₅ ≅ H ⊂ G , unless we expand a degree 4 vertex v into vertices x, y ∈ H both of degree 3. Then if we divide the degree 3 vertices of H into y, y', y'' which are connected to x by a path, and the others x, x', x'', this shows H contains a TK_3,3 .
3. In part (iv) of the algorithm, convince yourself that if none of the listed obstructions occur, then it is possible to insert the necessary vertex y and its neighbor, obtaining G from G''.
4. Show how to modify a plane drawing of a graph so that any given vertex or edge is on boundary of the infinite region.
   Extra Credit: If the original drawing has straight-line edges, find a way to do the above process that keeps the edges straight.

1. G = K₅ - {45}. Apply the algorithm via the contracted graph G' = G/xy with x = 3, y = 4; and alternatively with x = 4, y = 3. Answer: The graph is shown to be planar, built from a plane drawing of K₄ = G/xy.
2. The graph with vertices {1,...,5} and edges {12, 34, 15, 25, 35, 45, 13, 24}. Answer: The graph is planar.
3. G = K₆ - { i(i+1) for i = 1,...,6 }. That is, remove the outer 6-cycle from the complete graph K₆ . Hint: G/14 is isomorphic to the previous graph. Answer: Draw a 4-cycle with vertices 2,5,3,6; then inside the cycle draw 1 adjacent to 3,5, then draw 4 adjacent to 1,2,6.
4. G = Peterson graph on vertices {1,...,10}, with a 5-cycle 1,2,3,4,5; another 5-cycle 6,8,10,7,9; and five edges i(i+5) for i = 1,...,5. This can be drawn as a small 5-point star inside a large pentagon, with each vertex of the star connected to the closest vertex of the pentagon. Answer: Despite its shape, this graph cannot contain a TK₅ since each vertex has degree 3.Instead, G - {16,68,69} is clearly a TK_3,3 .
5. Addition: G is one of the graphs in HW 2/11 #1c,d,e. These can be taken as examples of the Algorithm cases (i), (ii), (iii).
6. Addition: G = the hypercube graph from HW 2/11 #1b.

1. Apply this to write the Taylor series of f(x) = 1/(1−x) = (1−x)⁻¹. Write the answer in "dot-dot-dot" notation (writing out enough terms to make the pattern clear, then "..."), and also in Σ notation.
   Answer: 1/(1−x) = 1 + x + x² + x³ + ... = ∑_k≥0 x^k This is the geometric series, the most important of all power series.
2. Use the geometric series to evaluate the infinite sum 1 + 1/3 + 1/3² + ... and the repeating decimal 0.11111....
3. Apply Taylor's Formula to write the series of f(x) = log(1+x) , using the derivative log'(z) = 1/z . That is, compute the coefficients a₀, a₁, a₂,...., until you see the pattern.
   Answer: log(1+x) = x − x²/2 + x³/3 − x⁴/4 + ... = ∑_k≥1 (−1)^k+1x^k / k .
4. Approximate log(3/2) by substituting x = 1/2 into your Taylor series, and adding the terms up to x⁴. How good is the approximation?
5. For which values of x are the above Taylor series formulas valid? For example, could we compute log(3) by substituting x = 2?
   Answer: The formulas hold only when the series converge to a finite value, namely for |x| < 1 . The series for log(1+x) also converges for x = 1, giving the remarkable formula: log(2) = 1 − 1/2 + 1/3 + 1/4 − ....

1. Suppose you have 2 apples and 2 bananas and you put any or all of them in your lunch bag, for example 0 apples and 2 bananas, which we can think of as the multi-set {B,B} . (Recall that a multi-set is an unordered collection of objects with repeats allowed.) What are all the possibilities for the contents of the bag? Figure this by logically expanding the expression:
   (0A or 1A or 2A) and (0B or 1B or 2B)
   using the logical distributivity rule from above. Expand until you have an expression like:  (0A and 0B) or (0A and 1B) or .... or (2A and 2B)
2. Re-do the entire computation in (a), replacing 0A, 0B by x⁰;  1A, 1B by x¹;  2A, 2B by x²;   "or" by + ;  "and" by ×.  Start with f(x) = (x⁰ + x¹ + x²) (x⁰ + x¹ + x²) and expand using algebraic distributivity. Collect like terms to get a polynomial a₀ + a₁ x +...+ a₄ x⁴ . That is, f(x) is the generating function of the coefficient sequence {a_k}.
   Question: What is the combinatorial meaning of the coefficients a₀,...,a₄? That is, what do these values count about ways of filling the bag?
   Answer: On expanding, we end up with 9 terms: x⁰x⁰ + x⁰x¹ + x⁰x² + x¹x⁰ + x¹x¹ + x¹x² + x²x⁰ + x²x¹ + x²x² corresponding to the 9 allowed multisets {}, {B}, {B,B}, {A}, {A,B}, {A,B,B},{A,A}, {A,A,B}, {A,A,B,B} . Each term xⁱx^j corresponds to a multiset with i apples and j bananas, so its exponent k = i+j is the total pieces of fruit. The coefficient a_k is the number of such terms, i.e., the number of ways to bag k pieces of fruit.
3. Now expand f(x) = (1 + x + x²)² again, this time using the binomial theorem (a+b)² = a² + 2ab + b² twice: first with a = 1,  b = x + x², and then again with a = x,  b = x². Thus, re-compute the coefficients a₀,...,a₄.
   Answer: (1 + x + x²)² = 1 + 2(x+x²) + (x+x²)²
         = 1 + (2x + 2x²) + (x² + 2 x x² + (x²)²)
   = 1 + 2x + 3x² + 2x³ + x⁴ . Thus there is 1 way to give no pieces, 2 ways to give 1 piece, 3 ways to give 2 pieces, etc.

1. We obtained the formula: a₅ = (52 | 5) (5 | 0) + (52 | 4) (4 | 1) + (52 | 3) (3 | 2) . Prove this formula directly by the sum and product principles. That is, split the problem into 3 cases, each giving one of the terms in the answer.
   Answer: Case 1: 5 distinct cards, (52 | 5). Case 2: one double, i.e. 4 distinct cards and one of the four doubled, (52 | 4)(4 | 1). Case 3: two pairs of doubles, i.e. 3 distinct cards and 2 of the 3 doubled: (52 | 3)(3 | 2).
2. Extra Credit:   Similarly, give a direct proof of the general formula: a_k  =   ∑_i=0^⌊k/2⌋ (52 | k-i) (k-i | i) .

1. Step 0:  Generalize the problem by letting a_k be the number of k-card hands dealt from a triple deck.
   Step 1:  Reduce the choice of a hand to a sequence of simple choices to give a neat product formula for f(x). Hint: You can simplify your answer further by writing 1 + x + x² + x³ = (1 + x) (1 + x²) Answer: f(x)   =   (1 + x + x² + x³)⁵²   =   (1 + x)⁵² (1 + x²)⁵². Step 2:  Use algebra (especially the Binomial Theorem) to expand the product expression for f(x), obtaining an explicit formula for a_k.
   Hint: Start with (1 + x)⁵² = ∑_i (52 | i) xⁱ    and    (1 + x²)⁵² = ∑_j (52 | j) x^2j
   Answer: f(x)   =   (1 + x)⁵² (1 + x²)⁵²  =   ( ∑_i (52 | i) xⁱ ) × ( ∑_j (52 | j) x^2j )

     =   ∑_i ∑_j (52 | i) (52 | j) x^i+2j   =   ∑_k [ ∑_i+2j=k (52 | i) (52 | j) ] x^k

   so: a_k = ∑_(i+2j=k) (52 | i) (52 | j) where, for a given k, the summation runs over all i,j ≥ 0 such that i+2j = k . For k = 5, the allowed pairs are (i,j) = (1,2) , (3,1), (5,0), so the number of 5-card hands from a triple deck is:

   a₅ = (52|1) (52|2) + (52|3) (52|1) + (52|5) (52|0) = 3,817,112 .

   To make this computation more understandable, use ellipsis (+ ...) notation instead of summations:

   f(x)   =   [ 1 + (52 | 1)x + (52 | 2)x² + (52 | 3)x³ + (52 | 4)x⁴ + (52 | 5)x⁵ + ... ]
   × [ 1 + (52 | 1)x² + (52 | 2)x⁴ + ... ]                                    Now multiply out and collect all the x⁵ terms to get a₅ .
2. Extra Credit  Explain the formula for a₅ using only elementary counting principles.
3. Extra Credit   Generalize the above arguments to the case of n decks for various n, say n = 4,5,6. For example, what can you make of: 1 + x + ... + x⁵ = (1 + x)(1 + x + x²)(1 - x + x²) .

1. How many ways are there to choose 20 jellybeans of 3 kinds (red, green, yellow)? Hint: Think of a bag of 20 jellybeans is a multiset of letters R,G,Y. Repeat our argument from class for counting multisets, where we computed (n multi-choose k) = ((n | k)) = n(n+1)(n+2)...(n+k−1) / k! .
2. You Can't Have Just One. How many ways are there to choose 20 jellybeans of 3 kinds, with the rule that you cannot choose just one of any kind? That is, if you choose any reds, you must take at least 2 of them, and the same way with greens and yellows.
   Answer:
   Step 0: Generalize the problem to give a sequence. Let a_k be the number of ways to choose k jellybeans with the given rule.
   Step 1. Form the generating function f(x) = ∑_k≥0 a_k x^k . To find a simple formula for f(x), consider that a handful of beans can be chosen by the logical expression: (0R or 2R or 3R or ...) and (0G or 2G or 3G or ...) and (0Y or 2Y or 3Y or ...) which translates to the algebraic expression: f(x) = (1 + x² + x³ + ...)³ = ( 1 + x²/(1-x) )³. Step 2. To expand the above expression for f(x), first apply the binomial theorem (a+b)³ = a³ + 3a²b + 3ab² + b³ , then expand each term using 1/(1-x)ⁿ = ∑_k≥0 ((n | k)) x^k . f(x) = 1 + 3x²/(1-x) + 3x⁴/(1-x)² + x⁶/(1-x)³            
   = 1 + 3x² + 3x³ + 6x⁴ + 9x⁵ + ∑_k≥6 [3 + 3((2 | k-4)) + ((3 | k-6))] x^k The coefficient at k = 20 is: 3 + 3((2 | 16)) + ((3 | 14)) = 3 + 3×17 + 16×17/2 = 174 . Extra Credit: Explain the above formula for a_k by elementary means.

1. Given that r₁ = r₂ = 1, r₃ = 2, r₄ = 4, r₅ = 9, compute r₆ and r₇ using the First and Second Recurrence Formulas (in Notes 3/14 and 3/19 below). Is the second formula simpler?
2. In Notes 3/14 below, we used the First Recurrence Formula to compute:

   r₅   =  ((r₁ | 4)) + ((r₁ | 2)) ((r₂ | 1)) + ((r₂ | 2)) + ((r₁ | 1)) ((r₃ | 1)) + ((r₄ | 1))
     =  1 + 1 + 1 + 2 + 4   =  9 .

   Verify this using the combinatorial recurrence: construct the 9 rooted trees by adding a new root to multi-sets of smaller rooted trees. For example, the second term of the formula corresponds to the unique multiset H with two 1-vertex trees and one 2-vertex tree: H   =  { ® , ® , ®−−O } , which produces a 5-vertex tree T by attaching a new root to each of the roots in H:

   T   =		®−−	®	−−®	−−O
   			|
   			®

   Do this for all the other terms.
   In fact, the First Recurrence Formula is a straight-forward consequence of the combinatorial recurrence; generating functions are not really needed.

3. Extra Credit: Can you prove the Second Recurrence Formula by a combinatorial correspondence, or in any way without generating functions? I don't know any way to do this.

1. Show that the generating function of the sequence is:

   f(x)  =  ∑_k≥0 c_k x^k  =  (1 − x)⁻¹(1 − x⁵)⁻¹ .

   Hint: Break the choice of a handful of change into two simple choices, and translate into algebra so that the exponent of x is the value of the handful.
2. Use the dlog method to find a recurrence for c_n. That is, take x d/dx log of both sides, as we did for the First Recurrence for rooted trees, and simplify to give a recurrence

   c_n+1 = an expression in c₀,...,c_n .

   Hint: As for trees, write the left side as x f '(x) / f(x) and simplify the right side starting with log(ab) = log(a) + log(b). Then clear denominators and equate coefficients.
3. Find a simpler recurrence from expanding the formula:

   f(x) (1 − x)(1 − x⁵)  =  1  =  1 + 0x + 0x² + ....

   This shows the dlog method does not necessarily give the best recurrence.
4. Find an explicit, non-recursive formula for c_n by using

   (1 − x)(1 + x + x² +x³ + x⁴)  =  1 − x⁵

   to write:

   f(x)  =  ∑_k≥0 c_k x^k  =  (1 + x + x² +x³ + x⁴) (1−x⁵)⁻² .

   The result shows that this is really a trivial problem, and fancy methods are wasted on it.
   Hint: Use (1 − z)⁻² = ∑_k≥0 ((2 | k)) z^k , where ((2 | k)) = k + 1.
5. Verify each of the above formulas by using it to compute c_n for n = 5, 6, 7, 8, 9, 10.
6. Extra Credit: Do all the same for handfuls of pennies, nickels and dimes, which is a less trivial problem.

   Answers: (b)    c_n  =  ¹/_n ∑_1≤i≤n c_n−i + ⁵/_n ∑_{1≤j≤⌊n/5⌋} c_n−5j   for n ≥ 1, where ⌊⌋ means round down.
   (c)    c_n  =  c_n−1 + c_n−5 − c_n−6   for n ≥ 1, where we take c_k = 0 for k < 0.
   (d)    c_n = ⌊n/5⌋ + 1   for n ≥ 0.

1. For each of the t_n = 6 unrooted trees T, determine:
   • p_T, the number of symmetry classes of vertices;
   • q_T, the number of classes of non-flipped (non-symmetry) edges;
   • the quotient tree T.
   Verify Otter's Lemma that T is indeed a tree and q_T = p_T − 1 .
2. For each T, list the distinct rooted trees T ' that are formed by designating one vertex of T as the root.
   Example: the path T = P₆ has T = P₃, the path with p_T = 3 vertices and q_T = 2 edges. The associated T ' are formed by marking the first, second, or third vertices as the root (corresponding to the vertices of T).
3. Compute r₆ = ∑_T p_T , and verify this number from previous HW.
4. For each T, list the corresponding distinct edge-rooted trees T". That is, we designate one of the q_T inequivalent non-flipped edges of T as a root edge. For each such T", draw the set of unequal vertex-rooted trees {T₁', T₂'} obtained by removing the root edge (but keeping its endpoints).
   Example: The path T = P₆ has q_T = 2 possible distinct edge-roots (since the middle edge is flipped by a symmetry and is not allowed to be a root). Removing the first edge gives {P₁ , P₅}; removing the second edge gives {P₂ , P₄}. Removing the flipped edge would give the multi-set {P₃ , P₃}, but we exclude this case.
5. Compute e_n = ∑_T q_T the number of edge-rooted trees, and verify the formula: e_n  =  ½[ ∑_1≤i≤n r_i r_n−i  −  r_n/2 ] .
6. Finally, verify Otter's Formula:

   t_n  =  r_n  −  e_n  =  r_n  −  ½[ ∑_1≤i≤n r_i r_n−i  −  r_n/2 ] .

   Display the trees corresponding to each term in this formula.

1. Rooted vs unrooted trees. We stated in class that asymptotically:

   r_n ∼ b aⁿ n^−3/2,             t_n ∼ c aⁿ n^−5/2,            

   where we use the constants:

   a ≅ 2.9558,      b ≅ 0.4399,      c ≅ 0.5349 .

   Any of the n vertices of an unrooted T may be chosen as the root, but only p_T of these give distinct rooted trees. Thus, if p_n is the average of p_T over all n-vertex unrooted T, we have: r_n  =  ∑_T p_T  =  p_n t_n . From the above formulas, determine p_n asymptotically. If p_n ∼ α n for some constant α, this is the expected proportion of vertices of T (of any size) which are distinct up to symmetry.
2. Labelled vs unlabelled trees. Cayley's Formula states that there are nⁿ⁻² labelled trees.
   For a labelled tree L, any of the n! permutations of the vertices give an equivalent unlabelled tree T, but really there are only n! / g_T distinct L corresponding to T, where g_T = |Γ_T| = |Sym(T)|. If g_n is the average value of g_T, the number of labelled trees should be approximately:

   nⁿ⁻²  =  ∑_T n! / g_T  ≅  (n! / g_n) t_n .

   Using Stirling's Formula (corrected from class):   n! ∼ (2πn)^1/2 (n/e)ⁿ,   approximate g_n , the expected number of symmetries of an n-vertex tree. Does a typical large tree have many symmetries, or not?

1. G = T a tree. Derive the answer using (i), then again with (ii), and again with (iii). Hint: A forest with n vertices and m edges has n − m components.
2. G = K_n the complete graph. Use (i).
3. G = K_n−e for any edge e. Use (iii).
4. G = K_n1n2 the complete bipartite graph with n₁ = 1,2. Use (i).
   Extra Credit: Do this for general n₁, n₂.
5. G = C_n the cycle. Do twice: (ii) & (iii).
6. G = W_n+1 the wheel graph, a cycle C_n with an extra vertex in the center connected to all the other vertices. Use the previous answer, and (i).

1. For each of the polynomials computed in the previous problem, verify that a_n = 1 , a_n−1 = −m , a₀ = 0 .
2. Show that for any graph, a_n−2 is equal to (m choose 2) minus the number of triangles (3-cycles) in G. Verify this for each of the examples.
3. We stated Stanley's Theorem that (−1)ⁿ P_G(−1) equals the number of acyclic orientations of G (i.e., ways of giving a direction to each edge, without creating any oriented cycles). Verify this for each of the examples.

1. Recall that a bridge of G is a disconnecting edge e, so that G − e = G₁ ∪ G₂ (disconnected pieces). Show that: P_G(k)  =  ^(k−1)/_k P_G1(k) P_G2(k) .
2. Let G be a connected graph, and list its 2-blocks (maximal 2-connected pieces) and bridges as: B₁, B₂, ... , B_r . (Recall that these form part of the 2-block tree of G.) Show that: P_G(k)  =  k^−r+1 P_B1(k) ⋅⋅⋅ P_Br(k) .

1. G = K₃ , k = 3.
2. G = C₄ , k = 3 .
3. G = C₅ , k = 2 . Show directly that there exist neither proper colorings nor compatible pairs.

1. Verify that (i) P_K1(k) = k and (ii) P_G∪H(k) = P_G(k) P_H(k) , where G ∪ H means the disconnected union of graphs G and H. We know that P_G(k) can be computed for any graph G using only rules (i), (ii) along with (iii) the Deletion-Contraction formula .
   Problem: Perform this computation all the way through for G = C₄ .
   Hint: Do Deletion-Contraction until there are no edges left, then use (i), (ii).
2. Let P'_G(k) := (−1)ⁿ P_G(−k). We showed (Notes 4/9) that P'_G(k) also satisfies rules (i), (ii), (iii), modified slightly because of the minus signs, and that these rules are enough to compute P'_G(k).
   
   Problem: Repeat your computation from the previous part to compute P'_G(k) for G = C₄ .
3. Stanley defines P_G(k) to be the number of weakly compatible pairs (O,c), where O is an acyclic orientation of G and c is a k-coloring with c(u) ≥ c(v) for every oriented edge u→v ∈ O. Verify from the definitions that P_G(k) satisfies the same version of (i) and (ii) as P'_G(k).
   Theorem 1.2 states that P_G(k) = P'_G(k) for all G and k. The bulk of Stanley's proof is to verify the appropriate rule (iii) for P_G(k). This shows that P_G(k) and P'_G(k) can be computed according to the same rules, so they have the same value.
4. List all the weakly compatible pairs (O,c) for G = C₄ , k = 1, and verify that P_G(k) = 14 = P'_G(k).

1. Show that a proper k-coloring of G is equivalent to an acyclic orientation O along with set S of n elements chosen from {1,..,k}. Hint: Think of a proper n-coloring as a way of giving a rank to each player in a tournament. This is equivalent to a way of specifying who beats whom in any matchup of two players, which in turn is equivalent to an acyclic orientation. Argue similarly for a proper k-coloring for k ≥ n.
2. Show that a weakly compatible pair (O,c) is equivalent to O along with multi-set S of n elements chosen from {1,..,k}.
3. Using the above equivalences, show directly that P_G(k)  =  (−1)ⁿ P_G(−k) for this graph.

1. Find a simple formula for the generating function d(x) = ∑ d_n xⁿ .
2. Use the dlog method to find a recursive formula for d_n .
3. Use algebraic tricks to get an explicit formula for d_n . Hint: (1 + x + x² + ⋅⋅⋅ + x⁹)(1 − x) = 1 − x¹⁰.

Any other choice of root allows symmetries. Notice that the star tree cannot be rooted in any way to eliminate symmetries.

1. Our computation of r_n (the number of all rooted trees) was based on the combinatorial recurrence: a rooted tree with n+1 vertices is equivalent to a multiset of rooted trees with total n vertices. Find a similar recurrence for asymmetric trees.
2. Use the combinatorial recurrence to deduce a generating function identity similar to that for r(x) = ∑ r_n xⁿ , of the form: a(x)/x  =  ∑ a_n+1 xⁿ  =  product with exponents a_k .
3. Apply the dlog method to find a recurrence for a_n similar to the Second Recurrence for r_n .
4. Extra Credit: Let b_n be the number of unrooted, unlabelled trees which can be rooted to eliminate symmetries. For example b₅ = 2 counts the two shapes of trees above (but not the star tree). Can you find an anlaog of Otter's Theorem to compute b_n in terms of a_n ?

• Four vertices y',y'' ∈ N_G(y) and x', x'' ∈ N_G(y), distinct from each other and from x,y, whose order around C is: x', y', x'', y''. Then the graph consisting of {x, x', x'', y, y', y''} with the edges between them and the arcs of C between them, clearly forms a TK_3,3 ⊂ G.
• Three vertices x', x'', x''' ∈ N_G(x) ∩ N_G(y). Then the graph consisting of {x, x', x'', x''', y} with the edges and arcs of C between them, clearly forms a TK₅ ⊂ G.
• Four vertices x', x''' ∈ N_G(x) ∩ N_G(y) and with x'', x''' ∈ N_G(x), whose order around C is: x, x', x'', x''', x''''. Then the graph consisting of {x, x', x'', x''', x'''', y} with the edges between them and the arcs of C between them, clearly contains a TK_3,3 ⊂ G.