Doubt about proof of theorem giving the number of pairwise edge-disjoint spanning trees of a given simple connected graph

492 Views Asked by At

enter image description here I understood that $T$ is one of the spanning trees which has disjoint edges compared to other $k-1$ edges. then, $T$ has $|V(G)|-1$ edges.

What does the author say in the underlined statement? Isn't it a trivial thing?we know that $|\mathscr P-1|\leq|V(G)|-1$. Is it follow from this inequality and pigeonhole principle? How do I prove the converse?Where will I get the converse? I draw the example for the illustration of the theorem,enter image description here

dark blue edged and narrow red edged trees are two edge disjoint trees, what does the theorem say?

1

There are 1 best solutions below

7
On

The highlighted sentence would be better if it said: whenever $V_1, V_2, \dots, V_p$ is a partition of $G$, and $T$ is a spanning tree of $G$, $T$ must contain at least $p-1$ edges joining distinct parts.

One way to prove this claim is: if we delete all edges of $T$ that join distinct parts among the $V_1, V_2, \dots, V_p$, then $T$ becomes a forest with $p$ components (one on each $V_i$). But deleting one edge can only increase the number of components of a graph by at most $1$, so at least $p-1$ edges must be deleted to get from $1$ to $p$ components.

Another way, as suggested in the comments: consider the graph $T^*$ on $p$ vertices $\{v_1, v_2, \dots, v_p\}$ with an edge $v_iv_j$ whenever $T$ has an edge between $V_i$ and $V_j$. $T^*$ must be connected: if there were no way to get from $\{v_1, \dots, v_k\}$ to $\{v_{k+1}, \dots, v_p\}$ in $T^*$, there would be no way to get from $V_1 \cup \dots \cup V_k$ to $V_{k+1} \cup \dots\cup V_p$ in $T$. So $T^*$ has at least $p-1$ edges.

Once the claim is done, take the $k$ edge-disjoint spanning trees $T_1, T_2, \dots, T_k$ and apply the claim to them. Each $T_i$ has $p-1$ edges joining distinct parts of the partition $V_1, V_2, \dots, V_p$, and these must be different edges for each $T_i$ (because they're edge-disjoint). Altogether, we get $k(p-1)$ edges joining distinct parts, which was what we wanted.