Supplemental Problems for Graduate Graph Theory

Math 581, Spring 1999

Chapter 1

Problem 1.A1. Explain in detain how Aigner gets rid of isthmi (in maps, for the 4-coloring problem).

Problem 1.A2. Ditto, for loops.

Problem 1.A3. Concerning Theorem 1.5 if bridges are allowed: Is it still valid? If not, is it valid after modification?

Problem 1.A4. Define “bridge” (“isthmus”) for disconnected graphs.

Problem 1.A5. Why is |R| = 1 for a tree?

Chapter 2

Problem 2.A1. Give a proof of Theorem 2.3 that doesn’t require knowing the formula for the upper bound in advance. Also, explain where the proof fails for the sphere.

Problem 2.A2. Give a proof of 2.5–2.6 by graph coloring rather than map coloring.

Problem *2.A3. (Research problem.) Define “countries” for drawings with crossings. (In the plane, if you wish.) Does there exist an Euler-type formula?

Problem 2.A4. (Research problem.) Define a “function” f : G → G′.

Problem 2.A5. We define G ≅ G′ to mean there exists an isomorphism f : G → G′. Can you simplify the definition of f, if all you want to say is when G ≅ G′ and you don’t care whether you state an actual definition of an isomorphism f? Hint: Similar to definiton of isomorphism for simple graphs.

Problem 2.A6. Prove the following theorem.

Theorem 2.A1. Let G be any class of graphs such that for each G ∈ G, every induced subgraph of G is also in G. If every graph in G has minimum degree < k, then every graph in G has chromatic number χ(G) ≤ k.

Problem 2.B1. What is the relationship between (a) map isomorphism, and (b) simultaneous isomorphisms G ≅ H and G^{∗} ≅ H^{∗}?

Problem 2.B2. In Aigner’s definition of map isomorphism, is it necessary to explicitly preserve vertex-country incidence, or does that follow automatically from the rest of the definition?

Problem 2.B3. We’re looking for smallest graphs that have more than one planar (i.e., spherical) embedding up to isomorphism.

(a) What is the (or a, if not unique) simple graph with the fewest vertices?

(b) The (or a) loopless graph with the fewest vertices? With the fewest edges? Amongst all such, that with the fewest edges?

(c) The smallest number of edges on one vertex? (Kyle found that 3 edges suffice and, I think, that 2 edges do not. So we should have this one done.)

Chapter 3

Problem 3.A1. Let’s define a graph G_{5} :

V (G_{5}) = P^{2}({1, 2, 3, 4, 5})

and ij and kl are adjacent if {i, j} ∩ {k, l} = ∅.

(a) What familiar graph is this?

(b) What is the group of automorphisms, Aut G_{5} ? How is it related to the “automorphism group” of the underlying set, i.e., the symmetric group S_{5} ?

(c) For any given automorphism f : G_{5} → G_{5} , how much of the action of f do you need to know to determine f completely?

Problem 3.A2. Generalize the construction of G_{5} in Problem 3.A1. (There are undoubtedly many answers to this question.)

Chapter 4

Problem 4.A1. Prove: If H is a Whitney dual of G, then G is a Whitney dual of H.

Problem 4.A2. Prove that a planar dual G^{∗} of a plane graph G is a Whitney dual of G.

Problem 4.A3. [This problem is not quite correct as stated. See 4.A3′ for a correct form of the important part. Can you find a correct version of this problem?] Prove: If B = E(X, Y) is a bond in G such that G:(X ∪ Y) is connected , then

(a) G:(X ∪ Y) is a connected component of G and

(b) G:X and G:Y are connected.

And conversely.

Problem 4.A3′. Prove:

(a) Every bond B in a graph G can be written in the form B = E(X, Y) where G:(X ∪ Y) is a connected component of G and G:X and G:Y are connected.

(b) Conversely, any edge set of that form is a bond.

Problem 4.A4. Prove: If e ∈ E(G) is subdivided into e_{1} and e_{2} to produce H and if H^{∗} is a Whitney dual of H, then

(a) every bond of H^{∗} that contains e_{1}^{∗} or e_{2}^{∗} contains both e_{1}^{∗} and e_{2}^{∗}, and

(b) [Corrected.] e_{1}^{∗} and e_{2}^{∗} are parallel edges or are both loops.

Problem 4.A5. Prove: If e and f are a series pair of edges in an arbitrary graph H, and if H^{∗} is a Whitney dual of H, then e^{∗} and f^{∗} are parallel edges. Show how this applies to Problem 4.A5.

Problem 4.A6. Find an example where e, f are not adjacent but are in series.

Problem 4.A7. Suppose E(X, X^{c}) and E(Y, Y^{c}) are cutsets in a graph. Find an expression for their “sum” (i.e., symmetric difference).

Chapter 5

Unimodality

Suppose we have a sequence {a_{0}, a_{1}, …, a_{n}} of numbers. We call it unimodal if

a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{m} = ⋯ = a_{M} ≥ ⋯ ≥ a_{n}

for some m, M with 0 ≤ m ≤ M ≤ n. It is concave if

a_{j} ≥ \frac{(j − i)a_{i} + (k − j)a_{k}}{k − i}

for all i < j < k. It is logarithmically concave (briefly, log-concave) if

a_{j}^{2} ≥ a_{j−1}a_{j+1}

for all 0 < j < n, and it is binomially (log-)concave if

\frac{a_{j}^{2}}{a_{j−1}a_{j+1}} ≥ \begin{matrix}\binom{n}{j} & 2 \\ \binom{n}{j−1} & \binom{n}{j+1} \end{matrix}

for all 0 < j < n. (The last name is a natural one but possibly my own invention. The term strongly log-concave has been used.)

In each type, if we replace the weak inequalities by strict ones, we call the property strict: e.g., strict binomial concavity. With weak inequalities we may call it weak.

Newton’s Theorem. If a polynomial has real zeros, then its coefficient sequence is binomially concave.

Problem 5.A1. Assume all a_{i} > 0.

(a) Among these four properties (the weak ones, that is), which ones imply which others? I propose (having been corrected) that concavity and binomial concavity each imply log-concavity and this implies unimodality, but no implications hold that aren’t implied by these. Prove all these claims.

(b) The same for the strict properties. (I believe this is possible by minor modifications to the proofs in (a); if it’s harder than that, don’t bother. You may just explain the necessary modifications and check them yourself without formally writing up the modified proofs.)

Problem 5.A2. Prove that concavity is equivalent to the following property, which we might call nearest-neighbor concavity (but it is actually the usual definition of concavity of a sequence):

a_{j} ≥ \frac{a_{j−1} + a_{j+1}}{2}

for 0 < j < n.

Problem *5.A3. Decide whether the coefficients of the chromatic polynomial of a graph are binomially concave. If you find a counterexample, be sure and tell me. If you find a proof, be sure and write your Ph.D. thesis.