Let G=(V,E) be a simple graph.a) Let A,B be a subsets of E, and spanning subgraphs of G with edges A,B,A∪B and A∩B have a,b,c and d connected components respectively. Prove that a+b≤c+d.We say that subsets A1,A2,…,Am of E have (R) property if and only if for each I⊂{1,2,…,m} the spanning subgraph of G with edges ∪i∈IAi has at most n−∣I∣ connected components.
b) Prove that when A1,…,Am,B have (R) property, and ∣B∣≥2, there exists an x∈B such that A1,A2,…,Am,B\{x} also have property (R).Suppose that edges of G are colored arbitrarily. A spanning subtree in G is called colorful if and only if it does not have any two edges with the same color.
c) Prove that G has a colorful subtree if and only if for each partition of V to k non-empty subsets such as V1,…,Vk, there are at least k\minus{}1 edges with distinct colors that each of these edges has its two ends in two different Vis.
d) Assume that edges of Kn has been colored such that each color is repeated [2n] times. Prove that there exists a colorful subtree.
e) Prove that in part d) if n≥5 there is a colorful subtree that is non-isomorphic to K1,n−1.
f) Prove that in part e) there are at least two non-intersecting colorful subtrees. inductioninequalitiescombinatorics proposedcombinatorics