MATH 370 Graph Theory and Combinatorics Fall 2022 Problem Set 06
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.
2022-12-02