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

MAT344H1Y– Problem Set 5

Introduction to Combinatorics

Due: June 16, 11PM

Complete the following exercises from the textbook in § 5 but do not submit them for credit: .  13-17, 19, 21, 28-35. Also do 18 and 20 if you are interested.

Complete the following problems for credit.  You must link to the problems on Gradescope. Answer all questions with full and complete explanations. The textbook is a good guide for what standard we are expecting of your explanations. Some questions may not be graded closely so that others may be focused on more closely in grading.

1. Explain why a n-colouring of a graph G  =  (V,E) is equivalent to a graph homomorphism f : G → Kn .

2. Suppose that G = (V,E) and H = (F,W) are graphs. Define the graph KG,H  to be the graph whose vertices are V ⊔ W, and whose edges is E ⊔ F ⊔ {xy  :   x ∈ V,y  ∈ W}.  Show that χ(KG,H ) = χ(G) + χ(H).

A directed graph is a pair G = (V,E) where V is a set of vertices, and E is a set of ordered pairs, (x,y) of elements x,y ∈ V with x  y .  If (x,y) ∈ E, we interpret that as an edge with an arrow from x to y . We will call a directed graph proper if for each two vertices x,y, at most one of (x,y) and (y,x) appears in E . Given a directed graph G = (V,E), we say it’s underlying undirected graph is the graph G\  = (V,E\ ) where xy ∈ E\  iff (x,y) ∈ E or (y,x) ∈ E .

3. A tournament is a proper directed graph whose underlying undirected graph is a complete graph. We say that a tournament is transitive if for any three vertices x,y,z, if (x,y) an (y,z) are directed edges in the graph, then (x,z) is a directed edge as well. Prove that every transitive tournament contains a winner (a winner is a vertex, w, such that if x is any other vertex, then (x,w) is a directed edge).

4. Suppose that G is a tournament with at least 2n  vertices.  Show that G contains a subgraph that is a transitive tournament with n + 1 vertices. (Hint: pick a vertex, x. Explain why there are either 2n −1  vertices with an edge going to x, or 2n −1  vertices with an edge coming from x)