## 这个作业是完成一些数学复习题目的数学作业代写

MATH 465 WINTER 2020: REMARKS BEFORE EXAM 2

Part I: administered through Canvas Quizzes. It has the same format as quizzes (True/False and Multiple Choice), but you will have 15 questions to complete in 45 minutes. You do not need to submit written work for these questions, just submit your final answers to Canvas within the time allowed, as you normally do for quizzes.

Part II: written responses to problems requiring justification (eg. proofs). The problems will be posted as a pdf on Canvas, and you will submit your responses to Gradescope (uploaded just like you do for homework).

• Both parts will be made available to you at 4:00pm ET on Wednesday, April 29. Both parts must be completed and submitted before 4:00pm ET on Thursday, April 30, giving you a window of 24 hours to complete these tasks (which encompasses our previously scheduled time for the in-person exam). This is to minimize conflicts with other exams, internet access, and different time zones.

• I expect that, if you study and are prepared, the exam should not take you more than two hours to complete. That said, I highly recommend that you do not wait until the last minute to complete the exam.

• You are allowed to use textbooks and class notes during the exam. However, you are prohibited from using the internet and from discussing exam questions with any person other than the instructor. This is enforced through the honor system; I will ask you to sign a statement (submitted with Part II) confirming that you have understood and followed these rules.

• My personal advice is to spend time studying for the exam and preparing a 3”× 5” note card, similar to your preparation for the midterm exam.

• If any questions on the exam are unclear, you are welcome to email me for clarification. I will do my best to reply promptly, but understand there may be a delay.

On the last page of this document, you will find the “cover page” for Exam 2. This includes the academic honesty statement that you will need to sign, a breakdown of points, and a summary of instructions. Here is some more information about what to study:

• On the next page, you will find a list of relevant material for the exam. Recall that this exam is inherently but not directly cumulative. It tests material discussed after the first exam (i.e. graph theory), but it may involve ideas from before (e.g. counting techniques).

• You should study your old homework assignments, review any feedback on Gradescope, and look at the solutions. Even if you received full credit, there may be valuable feedback or alternative solutions, and some problems are graded only on completion.

• You should also study previous quizzes.

• On pages 2–4 of this document, you will find a list of practice problems.

Finally, I will not post solutions to the problems listed below. Instead, I will encourage you to use the discussion board on Canvas, where you can

• post a solution to one of the problems below,

• ask a questions, and

• answer another student’s question.

You can earn 1 (and only 1) point of extra credit for making a meaningful contribution to the discussion board; see Canvas for more details. Please do not post answers without justification, nor irrelevant and inappropriate comments. Please give your fellow students a chance to post their solutions.

1. RELEVANT MATERIAL

Chapter 9: Graphs, walks (including cycles, paths, trails), (closed) Eulerian trails, Hamiltonian cycles, directed graphs, graph isomorphism, complete graphs Kn, simple graphs, degrees of vertices deg(v), (induced) subgraphs.

Chapter 10: Characterizations of trees, spanning trees, forests, leaves, adjacency matrix, incidence matrix, Matrix-Tree Theorem.

Chapter 11: Proper vertex colorings, bipartite graphs and complete bipartite graphs Km,n, chromatic number χ(G), chromatic polynomial pG(k), deletion G − e and contraction G/e,

matchings in bipartite graphs, perfect matchings, Hall’s Theorem.

Chapter 12: Planar graphs, Euler’s formula, degrees of faces, Four-Color Theorem.

Chapter 13: Ramsey numbers R(a, b), monochromatic subgraphs.

Section 16.1: Posets, chains and antichains, Dilworth’s Theorem.

Other: Flows and cuts in networks, Max-Flow Min-Cut Theorem. [see notes on Canvas]

2. PRACTICE PROBLEMS

Problem 1. Determine whether the graph G depicted below is Eulerian and/or Hamiltonian.

Problem 2. Determine whether the graph G in Problem 1 is planar and/or bipartite.

Problem 3. Determine the chromatic number and the chromatic polynomial of the graph G in Problem 1.

Problem 4. Determine whether the graph G depicted below is Eulerian and/or Hamiltonian.

Problem 5. Determine whether the graph G in Problem 4 is planar and/or bipartite.

Problem 6. Determine the chromatic number and the chromatic polynomial of the graph G in Problem 4.

Problem 7. Determine the number of perfect matchings in the graph G from Problem 4.

Problem 8. How many simple graphs are there with vertex set [4]?

Problem 9. How many non-isomorphic simple graphs are there with 4 vertices?

Problem 10. Let n be a positive integer. Prove that there are at least B(n) forests on the vertex set [n]. [Recall that B(n) is the number of partitions of the set [n]]

Problem 11. Let n be a positive integer. Prove that there are at least p(n) non-isomorphic simple graphs with n vertices. [Recall that p(n) is the number of partitions of the integer n]

Problem 12. Consider a complete rooted k-ary tree: a rooted tree in which any branch (non-leaf) vertex has exactly k children. For a positive integer m, how many leaves are there in a complete rooted k-ary tree with m branches? [We’ve seen these trees for k = 2 before, when studying Catalan numbers]

Problem 13. Is it possible to color the edges of K8 with red and blue so that it does not contain a monochromatic K2,3?

Problem 14. Give an example of a simple connected bipartite graph G = (U, V, E) for which |U| = |V | but there is no perfect matching.

Problem 15. In a directed graph with 14 vertices, the outdegrees of the vertices are 10, 8, 8, 8, 8,6, 6, 6, 4, 4, 4, 4, 4, 4. Amazingly, every vertex has the same indegree. What is the indegree of each vertex? How many edges does the directed graph have?

Problem 16. How many edges are in a forest with n vertices and k trees?

Problem 17. For which positive integers n does the complete graph Kn have an Eulerian trail? a closed Eulerian trail?

Problem 18. For which positive integers n does the complete graph Kn have a Hamiltonian cycle?

For these n, how many Hamiltonian cycles does Kn have? [Here, we view two cycles as distinct if the subgraphs determined by their edges are not equal]

Problem 19. Suppose that we colored each edge of K17 red, blue, or green. Prove that there must be a monochromatic triangle (that is, a triangle whose three edges have the same color).

Problem 20. Let n ≥ 4 be an integer. Let G be the graph which is the union of Kn−3 and a 5-cycle C5 together with all possible edges between the vertices of these graphs. Show that χ(G) = n, yet G does not contain a subgraph isomorphic to Kn.

Problem 21. Prove Konig’s Theorem: Let ¨ G = (U, V, E) be a bipartite graph. The maximum number of edges in a matching is equal to the minimum size of a subset C of vertices for which every edge has an endpoint in C (called a vertex cover).

Problem 22. An acyclic orientation of a graph G is an orientation of all of its edges that does not create an oriented cycle. Let a(G) denote the number of acyclic orientations of a graph G. Compute a(G) when G is a tree and when G is a cycle.

Problem 23. Consider again the acyclic orientations from Problem 22. Prove that if G = (V, E) is simple and e ∈ E, then a(G) = a(G − e) + a(G/e).

Problem 24. Consider again the acyclic orientations from Problem 22. Prove that if G = (V, E) is simple and pG(k) is its chromatic polynomial, then a(G) = (−1)|V |pG(−1).

Problem 25. Consider the poset Pn = [2] × [n] ordered so that (a, b) ≤ (x, y) iff a ≤ x and b ≤ y.

An order ideal in Pn is a subset S of Pn such that if (x, y) ∈ S and (a, b) ≤ (x, y) then (a, b) ∈ S. Let

Qn be the set of order ideals in Pn, and consider it as a poset under inclusion (S ≤ T iff S ⊆ T).

(a) What is the length of a maximal chain in Qn?

(b) Construct a bijection between maximal chains in Qn and 2 × n tableau [Recall when we studied Catalan numbers that a tableau is a 2 × n matrix with entries from [n] so that rows and columns are increasing].

Problem 26. What is the smallest possible number of edges in a connected graph with n vertices?

What is the largest possible number of edges in a disconnected simple graph on n vertices?

Problem 27. Prove that every connected graph G = (V, E) with at least two vertices has a vertex v such that the induced subgraph on V \ {v} is connected.

Problem 28. Prove that in any simple graph, there exists two vertices with the same degree.

Problem 29. Determine whether the two graphs depicted below are isomorphic.

Problem 30. Let G = (V, E) be a loopless graph with incidence matrix M and Laplacian matrix L.

Prove that L = MM>.

Problem 31. Let G = (V, E) be a loopless graph with no isolated vertices (i.e. no vertices of degree 0). Let A be the adjacency matrix of G. Prove that the diagonal entries of A4 are all positive.

Problem 32. Let G be a loopless graph with adjacency matrix A. Prove that if the (i, j) entries of A5 and A6 are both positive for some fixed indices i < j, then G contains a cycle of odd length.

Problem 33. Suppose that G is a simple, bipartite, planar graph, and that every vertex of G has degree d. What is the largest possible value of d?

Problems 34–50. Prove or disprove each of the following statements.

34. A simple graph with n vertices must have at least n − 1 edges.

35. There exists a simple graph on 6 vertices whose degree sequence is (4, 4, 4, 2, 1, 1).

36. There exists a simple graph on 6 vertices whose degree sequence is (4, 4, 4, 2, 1, 1).

37. There exists a simple graph on 5 vertices whose degree sequence is (4, 4, 3, 2, 1).

38. There exists a graph on 7 vertices whose degree sequence is (6, 5, 3, 3, 2, 1, 0).

39. There exists a tree on five vertices whose degree sequence is (3, 3, 2, 1, 1).

40. There exists a bipartite graph with degree sequence (6, 6, 6, 5, 3, 3, 3, 3, 3).

41. There exists at least three non-isomorphic graphs, each with 4 vertices and 4 edges.

42. The graph G from Problem 1 has a subgraph isomorphic to K2,3.

43. A trail is a path.

44. If G is planar and χ(G) = 2 then G is Hamiltonian.

45. If G contains a subgraph isomorphic to K4 then χ(G) = 4.

46. If G = (U, V, E) is a simple bipartite graph which has a perfect matching, then |U| = |V |.

47. If G = (V, E) is a tree, and e ∈ E is an edge, then the deletion G − e is a graph which is not connected.

48. If A is a 0-1 symmetric matrix with diagonal entries equal to zero, then there is a simple graph G for which A = A(G).

49. If every edge e in the network G depicted below has capacity c(e) = 465, then the function

f defined by f(e) = c(e) for every edge e is a maximum flow in the network G.

s t

50. In the directed graph G depicted below, there is a directed path from s to t.

s t

MATH 465: INTRODUCTION TO COMBINATORICS EXAM 2

For Part I:

• You have 45 minutes to complete these 15 questions.

• These are True/False and Multiple Choice questions administered through Canvas Quizzes. You do not need to submit your work or justification.

For Part II:

• Unless otherwise stated, you must show all work and fully justify answers.

This includes clearly written proofs and clearly explained computations. You may cite facts discussed in class, unless said fact is precisely what you are asked to prove.

• The questions are written on the next page. Submit your solutions through

Gradescope.

For both Part I and Part II:

• Please read carefully. If any questions are unclear, request clarification (by emailing the instructor, bibby@umich.edu). You will not be given partial credit on the basis of having misunderstood a question.

• You are allowed to use your notes and textbooks, but you are not allowed to use the internet or discuss with any person (other than possibly the instructor).

In order to receive credit for this exam, you must sign the following academic honesty statement:

I understand the instructions and rules of this exam. I confirm that the solutions I am submitting are my own. I confirm that I have not consulted the internet, nor have I consulted or collaborated with any person on these questions.

Signature:

POINTS POSSIBLE

Part I.1-15. 15

Part II.A. 6

Part II.B. 5

Part II.C. 4

TOTAL 30