A Direct Proof of a Theorem on Detachments of Finite Graphs

Abstract

Let $G$ be a finite graph with vertices ${\xi }_1,\dots ,{\xi }_n$, and let $S_1,\dots ,S_n$ be disjoint non-empty finite sets. We give a new proof of a theorem characterizing the least possible number of connected components of a graph $D$ such that $V(D)=S_1\cup \cdots \cup S_n$, $E(D)=E(G)$ and, when an edge $\lambda$ joins vertices ${\xi }_i,{\xi }_j$ in $G$, it is required to join some element of $S_i$ to some element of $S_j$ in $D$ (so that, informally, $D$ arises from $G$ by splitting each vertex ${\xi }_i$ into $|S_i|$ vertices).