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

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,

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

• What book is this from? – Shaun Sep 22 '18 at 9:28
• The author meant that there are at least $|\mathscr{P}|-1=p-1$ edges of $T$ that connects vertices from different classes in $\mathscr{P}$. This is obvious if you collapse each $V_i$ to a point. – user10354138 Sep 22 '18 at 9:49
• @shaun Textbook of graph theory Balakrishnan and Ranganathan – Math geek Sep 22 '18 at 13:10
• T is a spanning tree, so graph uses every verices of G, each vertices are connected, so, it must have n-1 edges. each edge, one end is in any one of the $V_j$. so it must have p-1 edges of T . right?@user10354138 – Math geek Sep 23 '18 at 10:32
• Where can I find the converse? – Math geek Sep 23 '18 at 10:34

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.

• How do I prove the converse? – Math geek Sep 23 '18 at 16:11
• @Mathgeek I don't know; it seems hard. Have you tried looking up the citations Tutte [181] or Nash-Williams [145] in your book? They should correspond to papers cited at the end of the book or at the end of the chapter. – Misha Lavrov Sep 23 '18 at 16:22
• proof is not given in the textbook. from where will i get this paper? – Math geek Sep 24 '18 at 0:51
• Tutte [181] or Nash-Williams [145], what does that mean? – Math geek Sep 24 '18 at 0:52
• It means that somewhere in your textbook, there is a list of papers cited, and number 181 on this list is a paper by Tutte that proves this theorem. The paper may or may not be available online, but without knowing what the citation is, nobody else can say. – Misha Lavrov Sep 24 '18 at 1:15