1. (10%) (a) Assume that each vertex has a unique id, how many different spanning trees...

Transcribed Image Text:

1. (10%) (a) Assume that each vertex has a unique id, how many different spanning trees in the following figure? (5%) :vertex :edge (b) We can show that the set {(x,y) | x,y are positive integers} is countable by finding a 1-1 mapping from (x,y) to an integer. Given (1,1) -> 1, (1,2)->2, (1,3)->4, (1,4)->7, (2,1)-> 3, (2,2)->5, (2,3)->8, (3,1)->6, (3,2)->9, (4,1)->10, please find which (x,y) maps to 465? (5%) 1. (10%) (a) Assume that each vertex has a unique id, how many different spanning trees in the following figure? (5%) :vertex :edge (b) We can show that the set {(x,y) | x,y are positive integers} is countable by finding a 1-1 mapping from (x,y) to an integer. Given (1,1) -> 1, (1,2)->2, (1,3)->4, (1,4)->7, (2,1)-> 3, (2,2)->5, (2,3)->8, (3,1)->6, (3,2)->9, (4,1)->10, please find which (x,y) maps to 465? (5%)