Tutte] Every $2^k$-edge-connected graph has $k$ edge-disjoint spanning trees. Proof: Apply the matroid intersection theorem.

Anyone see how this proof is suppose to work?

  • $\begingroup$ I haven't found a proof yet, but I can see how matroid intersection will work for the case where $k=2$ ($k=1$ is clearly obvious). For $k=2$, consider the graphic matroid and it's dual. I've tried some variation of these matroids for larger $k$ but none of them work well. I will post an answer if I succeed to find one that works well. $\endgroup$ – user341124 Nov 17 '17 at 23:17

Call your graph $G=(V,E).$ Let $M_1$ be the direct sum of $k$ copies of the graphic matroid of $G,$ and let $M_2$ be the partition matroid where a set of edges $F\subseteq [k]\times E$ is independent iff each $e\in E$ is used at most once. The matroid intersection theorem says that $E$ can be split into $k$ disjoint connected spanning graphs if and only if

$$\min_{F_1,\dots,F_k\subseteq E}\left(r(F_1)+\dots+r(F_k)+\left|\bigcup_{i=1}^k (E\setminus F_i)\right|\right)= k(n-1)$$ where $r$ denotes the rank of the graphic matroid.

If an edge in some $F_i$ isn't in $\bigcap_{i=1}^n F_i,$ it might as well be removed - this won't increase the value inside the min. So the minimum is achieved when all the $F_i$ are equal. And then any edge between two vertices that are already connected in $F_1$ might as well be added to all the $F_i,$ again because this won't increase the value inside the min. With these reductions the only thing that matters is the connected components of $F_1.$ (Where if a vertex isn't used by any edge in $F_1,$ it counts as a separate component.)

Let $\mathcal P$ denote a partition of $V,$ let $\ell(\mathcal P)$ denote the number of components of the partition $\mathcal P,$ and let $|E\setminus \mathcal P|$ denote the number of edges that go between different parts of $\mathcal P.$ The condition reduces to

$$\min_{\mathcal P}(k(n-\ell(\mathcal P))+|E\setminus \mathcal P|)= k(n-1).$$

If your graph is $2k$-edge-connected then for any non-trivial partition each part must have at least $2k$ edges connecting it to other parts, giving at least $k\cdot \ell(\mathcal P)$ edges total. So the value inside the min is at least $kn$ for non-trivial partitions, and the minimum $k(n-1)$ is achieved by the trivial partition. To get the title result note that $2^k\geq 2k$ for $k\geq 1.$

  • $\begingroup$ Even though it's mentioned that we want to use the Matroid Intersection theorem, I think it's worth mentioning that this is more natural via the Matroid Partitioning Theorem (which is essentially equivalent to Matroid Intersection theorem). $\endgroup$ – user341124 Nov 21 '17 at 21:50
  • $\begingroup$ @ErlangWiratamaSurya: the Matroid Partitioning Theorem applied to the cographic matroid, right? I think the Matroid Union theorem also works well here, giving the first displayed formula without having to use a separate partition matroid. $\endgroup$ – Dap Nov 22 '17 at 11:54
  • $\begingroup$ From what I understand it should be applied to the graphic matroid, but maybe our statement of the matroid partitioning theorem are different. I'm actually quite new to matroid theory (just learned about this theorem this week in class) so I haven't learned about matroid union theorem. From a quick glance at the statement I think it's true that this problem is also a trivial application of the Matroid Union theorem. $\endgroup$ – user341124 Nov 25 '17 at 20:28

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.