Question $1(14$ marks$)$ Let $G=(V,E)$ be a connected, undirected graph.

a$)[7$ marks$]$ Assume that $T1=(V,E1),T2=(V,E2)$ and $T3=(V,E3)$ are spanning

trees of $G$ and that their sets of edges meet the following conditions: $E1E2=\frac{O}{?},$

$E1E3=\frac{O}{?}$ and $E2E3=\frac{O}{?}.(\frac{O}{?}$ represents the empty set.$)$

What is the smallest number of vertices that G can have? Explain your answer

and provide an example of such a graph. Clearly describe the $3$ spanning trees in

the example you provide.

b$)[7$ marks$]$ Let $G=(V,E)$ be a graph. Provide an algorithmic strategy that can find

and output exactly two spanning trees of $G$ that do not share any edges, e$.$g$.,$

$T1=(V,E1),T2=(V,E2)$ where $T1$ and $T2$ are spanning trees of $G$ and $E1E2$

$=\frac{O}{?},$ if such two spanning trees exist.

Provide your algorithmic strategy using pseudo code or a detailed description in

natural language. Explain why your algorithmic strategy meets the requirement.