Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH 370

Graph Theory and Combinatorics

Fall 2022

Problem Set 06

1.  (Exercise 5.7.11) Show that the complement of a disconnected graph is always con- nected.  Is the complement of a connected graph always disconnected?  Justify your claim.

2. Prove or disprove the following statements

(a) If G has no (edge) cuts, then G has exactly one cycle.

(b) If G has no cut points, then G has no (edge) cuts.

(c) If G has no (edge) cuts, then G has no cut points.

3. Let τ(G) denote the length of the longest path in G. Prove that χ(G) ≤ τ(G).

4. Provide an example of a non-planar graph with order greater than 5 such that less than 5 colors are needed to color the graph. Show the coloring.

5. Determine the chromatic number for a map of the United states.

6. Interpret a tournament as follows: the vertices are players.  If (v,w) is an arc, player v beat w . Say that v is a champion if for every other player w, either v beat w or v beat a player who beat w . Show that a player with the maximum number of wins is a champion. Find a 5-vertex tournament in which every player is a champion.