MATH 239: Assignment 6
MATH 239: Assignment 6
Submission due: March 03 at 11:00AM EST
Every question has 1 mark dedicated to presentation.
Copyright By PowCoder代写 加微信 powcoder
Question 1. (10 marks) For any positive integer n, consider the graph G = (V, E) that is an n-cube.
(a) Show that for every two distinct vertices u and v in V there are at least n edge disjoint uv-paths
in G. [Hint: Use induction on n.]
(b) Find X ⊊ V , X ̸= ∅ such that the cut induced by X has the minimum possible number of edges.
Justify your answer.
Question 2. (10 marks) Let k ≥ 2 be an integer. Suppose G has minimum degree at least k.
(a) Prove that G has a path of length at least k;
(b) Suppose in addition, G has girth at least l ≥ 3. Show that G has a cycle of length at least 2 + (l − 2)(k − 1) and G also has a path of length at least 1 + (l − 2)(k − 1).
Question 3. (10 marks) Using the definition of the complement G ̄ of a graph G given in Q8 of Problem set 4.4, prove that at least one of G, G ̄ is connected.
WINTER 2022 MATH 239: INTRODUCTION TO COMBINATORICS Page 1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com