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?

  • $\begingroup$ What book is this from? $\endgroup$ – Shaun Sep 22 '18 at 9:28
  • $\begingroup$ 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. $\endgroup$ – user10354138 Sep 22 '18 at 9:49
  • $\begingroup$ @shaun Textbook of graph theory Balakrishnan and Ranganathan $\endgroup$ – Math geek Sep 22 '18 at 13:10
  • $\begingroup$ 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 $\endgroup$ – Math geek Sep 23 '18 at 10:32
  • $\begingroup$ Where can I find the converse? $\endgroup$ – 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.

  • $\begingroup$ How do I prove the converse? $\endgroup$ – Math geek Sep 23 '18 at 16:11
  • $\begingroup$ @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. $\endgroup$ – Misha Lavrov Sep 23 '18 at 16:22
  • $\begingroup$ proof is not given in the textbook. from where will i get this paper? $\endgroup$ – Math geek Sep 24 '18 at 0:51
  • $\begingroup$ Tutte [181] or Nash-Williams [145], what does that mean? $\endgroup$ – Math geek Sep 24 '18 at 0:52
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Sep 24 '18 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.