Another proof of a theorem concerning detachments of graphs (Q1176032): Difference between revisions

Let \(f\) be a positive integer-valued function on the set of vertices of a graph \(G\). A graph \(H\) is called an \(f\)-detachment of \(G\) if \(H\) arises from \(G\) by replacing each vertex \(u\) of \(G\) by a set \(V(u)\) of vertices, \(| V(u)|=f(u)\), \(| E(H)|=| E(G)|\) and if \(x=uv\) is an edge of \(G\) then there is exactly one edge between \(V(u)\) and \(V(v)\). A new proof of the min-max theorem characterizing the minimum number of components among all \(f\)-detachments of \(G\) is given.