Abstract
Given an undirected graphG=(V, E) and a partition {S, T} ofV, anS-Tconnector is a set of edgesF¿Esuch that every component of the subgraph (V, F) intersects bothSandT. We show thatGhaskedge-disjointS-Tconnectors if and only if |dG(V1)¿…¿dG(Vt)|¿ktfor every collection {V1, …, Vt} of disjoint nonempty subsets ofSand for every such collection of subsets ofT. This is a common generalization of a theorem of Tutte and Nash-Williams on disjoint spanning trees and a theorem of König on disjoint edge covers in a bipartite graph.
| Original language | English |
|---|---|
| Pages (from-to) | 184-188 |
| Number of pages | 5 |
| Journal | Journal of Combinatorial Theory, Series B |
| Volume | 73 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 1998 |