$3$ Split Trees

In this question $G=(V,E)$ is an undirected connected graph with $n=|V|$ nodes and $m=|E|$ edges. Recall that a spanning subgraph of $G$ is any graph of the form $(V,E^{\text{'}})$ where $E^{\text{'}}$ is a subset of $G\text{'}$s

edges, i$.$e$.,E^{\text{'}}$subeE. A spanning tree of $G$ is any spanning subgraph which is connected and has $n-1$edges. Equivalently it is a connected graph without any cycles. The nodes of $V$ which have degree $1$ in a

spanning tree are called its leaves; let $L(T)$ denote the set of leaves of $T.$In this question we call a spanning tree $T=(V,E^{\text{'}})$ a split tree if the leaves of $T$ form an independent set in the original graph $G.$

$1)$ Show that if T is a spanning tree with $|$L$($T $)|>=3,$ then either G is a split tree, or there is a spanning tree with fewer leaves than T $.$

Hint: Design an algorithm which given a spanning tree T with $|$L$($T$)|>=3$and two leaves which are adjacent in G$,$ produces a new spanning tree T $$ with $|$L$($T $)|<mtext\; id="EditorElement\_346864"></mtext><mi\; id="EditorElement\_346865">|</mi>$L$($T $)|.$ Does your algorithm prove the following? STATEMENT: Every graph G has a spanning tree

which is a split tree? Either explain why or give a counterexample.