Math 465 Homework 12
Due: 11:59pm on Wednesday, April 15, 2020
Problem 1. Suppose that we color the edges of K6 with two colors (say, red and blue). Prove that
there are at least two monochromatic triangles.
Problem 2. Suppose that we colored each edge of K66 red, blue, green, or yellow. Prove that there
is a monochromatic triangle (that is, a triangle whose three edges have the same color).
[Note: This says R(3, 3, 3, 3) ≤ 66.]
Problem 3. Let n be a positive integer, and suppose that we color the edges of K2n−1 with two
colors (say, red and blue). Prove that if n is even, then there is a monochromatic K1,n.
Problem 4. Let n > 1 be an integer. Prove that R(n + 2, 3) > 3n.
[Hint: Homework 1 Problem 8]
Problem 5. Consider the network depicted below; the numbers near the edges are their capacities.
(a) Find a flow in the network with maximum value.
(b) Find a cut in the network with minimum capacity.
s t
2
3
3
3
2
1
2
3
4
1
3
1
2
Problem 6. Let G = (U, V, E) be a simple bipartite graph, and let k = |U|. You are not allowed to
use Hall’s Theorem in this problem (we’re going to prove the “hard” direction in part (e)).
(a) Define a network H = (W, A) on the vertex set W = U ∪V ∪ {s, t} with edges and capacities
given by:
• an edge e : u → v with capacity c(e) = 1 whenever u ∈ U, v ∈ V are adjacent in G,
• an edge e : s → u with capacity c(e) = 1 whenever u ∈ U, and
• an edge e : v → t with capacity c(e) = 1 whenever v ∈ V .
Construct a bijection between matchings in G and flows in H.
(b) Define a network H0 = (W, A) on the vertex set W = U ∪V ∪{s, t} with edges and capacities
given by:
• an edge e : u → v with capacity c(e) = k whenever u ∈ U, v ∈ V are adjacent in G,
• an edge e : s → u with capacity c(e) = 1 whenever u ∈ U, and
• an edge e : v → t with capacity c(e) = 1 whenever v ∈ V .
Prove that a function f : A → Z defines a flow in H if and only if it defines a flow in H0
.
(c) What is the relationship between the size of a matching in G and the value of the corresponding flow in H0?
(d) Prove that if there is no matching of U into V , then there exists a cut (X, Y ) in the network
H0
such that c(X, Y ) < k.
(e) Prove that if there is no matching of U into V , then there exists a set S ⊆ U such that
|S| > |NG(S)|.
Problem 7. Consider the bipartite graph G = (U, V, E) depicted below (left), and the corresponding
network H = (W, A) as defined in Problem 6(a).
(a) Find a flow in the network with maximum value.
(b) Find a cut in the network with minimum capacity.
(c) Find a matching in the bipartite graph with the maximum number of edges.
s t

EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue

EasyDue™是一个服务全球中国留学生的专业代写公司