✦ LIBER ✦

A short proof of kundu's k-factor theorem

✍ Scribed by Yong-Chuan Chen

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 301 KB
Volume: 71
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90070-2

No coin nor oath required. For personal study only.

✦ Synopsis

We give a very short proof of the following theorem on k-factorable degree sequences due to Kundu [5]: Tbearem 1. Let (dl,d2,-.-,d,,) and.(d,-k,,d,-k,,...,d,-k,) be two graphical sequences satisfying k s ki s k + 1, 1 bi s n, for some k PO. Then there exists a' graph G =: (V, E) which contains a subgraph F such that &(Ui) = di and dF(ui) = ki for alI UiE(U~#U~p.**,U~)= V(G). Our proof readily extends to derive the generalizations of the above theorem obtained by Kundu [6], Kleitman and Wang [4].

📜 SIMILAR VOLUMES

A short proof of K�nig's matching theore

A short proof of K�nig's matching theorem

✍ Rizzi, Romeo 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 43 KB 👁 2 views

We give a short proof of the following basic fact in matching theory: in a bipartite graph the maximum size of a matching equals the minimum size of a node cover.

A short proof of Chvátal's Watchman Theo

A short proof of Chvátal's Watchman Theorem

✍ Steve Fisk 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 45 KB

A very short proof of Dixon's theorem

✍ Shalosh B Ekhad 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 56 KB

A Short Proof of Mader's S-Paths Theorem

✍ Alexander Schrijver 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 78 KB

For an undirected graph G=(V, E) and a collection S of disjoint subsets of V, an S-path is a path connecting different sets in S. We give a short proof of Mader's min-max theorem for the maximum number of disjoint S-paths. 2001

A short proof of Martindale's theorem on

A short proof of Martindale's theorem on GPIs

✍ Chen-Lian Chuang 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 223 KB

A short proof for a generalization of Vi

A short proof for a generalization of Vizing's theorem

✍ Claude Berge; Jean Claude Fournier 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 1 views

## Abstract For a simple graph of maximum degree Δ, it is always possible to color the edges with Δ + 1 colors (Vizing); furthermore, if the set of vertices of maximum degree is independent, Δ colors suffice (Fournier). In this article, we give a short constructive proof of an extension of these re