(e) [3 points] .

(f) [3 points] 5 dividesn5 - n whenever n is a positive integer.

(g) I points Given a,bent and gcdta, band gcd(a，b)≠ 1 , we cannot find an inverse of a modulo b in some cases.

(a) [6 points) Compute the expected number of vertices and edges that remain after the deletion process.

(b) I6 pointsI Based on Ca), ty to infer that for any graph with n vertices with nd/2 edges, there is an independent set with at least n/2d vertices.

3. A treed that never gave up on its dream to flourish. [10 points] Let T be a spanning tre n edge cost function c. T is defined to have the cycle property if for any edge the cycle generated by adding e' to T. Also, T is defined to have the cut property if for any edge for all e' in the cut defined by e. Show that the following three statements are equiva 1. T has the cycle property. 2. T has the cut property. 3. T is a minimun cost spanning tree.

4. Respect for the ancients. [8 points Find an integer x such that x 1 (mod 3), x  3 (mod 7) and x 9 (mod11).

5. Show time! (10 points] Prove that for every positive integer n, there are n consecutive composite integers. In other words, prove that we can find n consecutive composite integers for any n.

(a) [6 points] Prove that any Sprouts game consists of a finite number of moves before someone loses. In other words, the game will terminate eventually.

(b) [7 points] Show a tight upper bound on the worst -case number of moves in a Sprouts game that starts with n dots, and prove your answer.

7. Act together, we go far. [12 points) Suppose we have two isomorphic graphs G1 and H1, as well as two isomor- phic graphs G2 and H2. Prove or disprove tha are also isomorphic.

110年 - 110台灣聯合大學系統_碩士班招生考試_電機類:離散數學#104950

110年 - 110 國立臺灣大學_碩士班招生考試_工程科學及海洋工程學研究所丁組:離散數學(A)#100758

109年 - 109 國立高雄大學_碩士班招生考試_資訊工程學系：離散數學#103285