Homework answers / question archive / Math 452: Graph Theory Question 1

Math 452: Graph Theory Question 1

Math

Share With

Math 452: Graph Theory

Question 1. (30 points) Assume that G and G0 on the same set of vertices. Let H be the graph on the same set of vertices, with an edge drawn if and only if it is an edge in at least one of G and G0 . Prove that χ(G) · χ(G0 ) ≥ χ(H). Note: This result implies an interesting inequality: χ(G) · χ(G) ≥ |V (G)|.

Question 2. (40 points) We know the trivial bound for the chromatic number χ(G) ≥ max  ω(G), |V (G)| α(G)  . We also know that the bound can be tight (i.e., the equality holds for some specific graph). This problem shows will show that the bound may be very loose. (a) For any positive integer k, construct a graph Hk such that χ(Hk) − |V (Hk)| α(Hk) > k. The following process is independent from part (a) and gives a family graphs in which the gap between χ(G) and ω(G) increases to infinity. Start with a graph G1 = G which does not contain a copy of K3. We call such graph G is “K3-free”. We construct Gk+1 from Gk as follows, for k ≥ 1. Make an independent copy G0 k of V (Gk). (Each vertex v ∈ V (Gk) has a copy v 0 ∈ V (G0 k ), and there is no edge in G0 k .) Connect each vertex v 0 in G0 k to the neighbors of the corresponding vertex v in Gk. Add a new vertex u, that is not in Gk and G0 k , and connect u to all vertices of G0 k . See Figure 1 for an example when G1 ∼= K2. (b) Prove that χ(Gk+1) = χ(Gk) + 1. (c) Prove that Gk is K3-free, for all positive integers k. (d) Show that for any positive integer N, there exist some k such that χ(Gk)−ω(Gk) > N. Math 452: Graph Theory Final Exam Due date 12/12/2022 (12:00 pm) Figure 1: From left to right: G1 ∼= K2, G2 ∼= C5, and G3. The red vertices indicates independent vertices in G0 k , and the blue vertex indicates the vertex u.

Question 3. (40 points) An “ear” of a graph G is either a path or a cycle with a distinguished vertex, called the “endpoint” of the cycle. • An ear decomposition of a graph G is a partition of its set of edges into a sequence of ears, such that: 1. The first ear is a cycle. 2. The endpoint(s) of each ear belong to earlier ear(s) in the sequence. 3. The internal vertices of each ear do not belong to any earlier ear. • An open ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct. See Figure 2 for an example. a) Proof that a graph G is 2-connected if and only if it has an open ear decomposition. b) Prove that any graph G is 2-edge-connected if and only if it has an ear decomposition.

Question 4. (30 points) Let G be a k-connected graph, for a positive integer k ≥ 2. Prove that for any k vertices of G, there exists always a circle containing them. Note: We already proved case k = 2 in the class. You do not need to reprove this case. Question 5. (20 points) Let T be a tree with t edges, for some positive integer t. Prove that if a graph G has average degree 2t, then it contains a copy of T. Question 6. (20 points) Let G be a graph with 99 vertices with 81 ≤ deg(v) ≤ 90, for any vertex v. Prove there exists a vertex w of G that has at least 10 neighbors, which have the same degree. Math 452: Graph Theory a b G1 G G G 2 3 4 G4 G3 G2 G1 Figure 2: (a) An ear decomposition, which is not open. (b) An open ear decomposition.