110年 - 110 國立嘉義大學_碩士班招生考試試題_資訊工程學系：離散數學#145518

1. Find two different spanning trees of the following graph. (20%)

2. (1)How many cards must be selected from a standard deck of 52 cards to guarantee that at least four cards of the same suit are chosen? (10%)

(2)How many cards must be selected to guarantee that at least four hearts are selected? (10%)

3. Find the recurrence relation and initial condition for 1, 7, 31, 127, 511, .... (10%)

4. Assume that A is a friend of B if and only if B is a friend of A. Show that for any N ≥ 2, there are two people in the group of N persons having the same number of friends. (15%)

5. Prove by induction \( \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \dots + \frac{1}{\sqrt{n}} > \sqrt{n} \). (15%)

6. Prove or disprove the following two graphs are isomorphic. (20%)