In: Advanced Math
For any n ≥ 1 let Kn,n be the complete bipartite graph (V, E) where V = {xi : 1 ≤ i ≤ n} ∪ {yi : 1 ≤ i ≤ n} E = {{xi , yj} : 1 ≤ i ≤ n, 1 ≤ j ≤ n} (a) Prove that Kn,n is connected for all n ≤ 1. (b) For any n ≥ 3 find two subsets of edges E 0 ⊆ E and E 00 ⊆ E such that (V, E0 ) and (V, E00) are spanning trees which are not isomorphic.
For any n ≥ 1 let Kn,n be the complete bipartite graph (V, E) where V = {xi : 1 ≤ i ≤ n} ∪ {yi : 1 ≤ i ≤ n} E = {{xi , yj} : 1 ≤ i ≤ n, 1 ≤ j ≤ n} (a) Prove that Kn,n is connected for all n ≤ 1. (b) For any n ≥ 3 find two subsets of edges E 0 ⊆ E and E 00 ⊆ E such that (V, E0 ) and (V, E00) are spanning trees which are not isomorphic.