Spanning tree with minimum number of leaves

discrete mathematicsgraph theory

Consider G is a connected graph with $\alpha(G) >= 2$ . Prove that G has a spanning tree with at most $\alpha(G)$ leaves.

My own idea is that we can consider that for example T is a spanning tree of G with minimum number of leaves. Then if we consider that T has more than $\alpha(G)$ leaves, then two of these vertices with degree one in T must be connected to each other in G (otherwise the independency number of G with be greater) , but I do not know how this helps…

Best Answer

Hint: Your idea is good. Using the fact that two leaves of $T$ must be joint by an edge in $G$, try to construct a spanning tree which has less leaves than $T$; this gets you a contradictiotn.

Proof:
Let $G$ be a graph on $n$ vertices with $\alpha(G)\geq 2$. Let $T$ be a spanning tree of $G$ with as few leaves as possible; denote the number of leaves of $T$ as $t$.
Suppose that $t>\alpha(G)$, then there exists two leaves in $T$, say $x,y$, such that $xy$ is an edge in $G$.

Consider the graph $T+xy$ obtained by adding the edge $xy$ to $T$; note that $T+xy$ has $t-2$ vertices of degree $1$. Since $T$ is a tree, ie a maximal acyclic graph, then there exists a cycle in $T+xy$ which contains $x$ and $y$, say $v_0v_1v_2...v_mv_0$, with $v_0=x$ and $v_m=y$.

Consider now the vertices $v_1,v_2,v_3...,v_{m-1}$ in $T$. If all of them have degree 2 then $xv_1v_2...v_{m-1}y$ is a connected component of $T$; since $T$ is connected this imples that $T=xv_1v_2...v_jy$ ie $T$ is a path. But a path has exactly $2$ leaves which implies $2>\alpha(G)$, contradiction.

Thus there exists some $i\in\{1,2,3,...,m-1\}$ such that $v_i$ has degree greater than $2$. Consider the graph $T'=T+xy-v_iv_{i+1}$ obtained by deleting the edge $v_iv_{i+1}$ from $T+xy$.
$T'$ is connected (since we removed an edge in a cycle) and has $n-1$ edges; thus $T'$ is a tree.
Note that by construction the degree of $v_i$ in $T'$ is grater than $1$, hence $T'$ has at most $t-1$ leaves.

We have constructed a spanning tree $T'$ with at most $t-1$ leaves. This contradicts the initial assumption that $T$ is a spanning graph with as few leaves as possible. Thus $t\leq\alpha(G)$.