𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Short proofs of classical theorems

✍ Scribed by J. A. Bondy

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
81 KB
Volume
44
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We give proofs of Ore's theorem on Hamilton circuits, Brooks' theorem on vertex coloring, and Vizing's theorem on edge coloring, as well as the ChvΓ‘tal‐LovΓ‘sz theorem on semi‐kernels, a theorem of Lu on spanning arborescences of tournaments, and a theorem of Gutin on diameters of orientations of graphs. These proofs, while not radically different from existing ones, are perhaps simpler and more natural. Β© 2003 Wiley Periodicals, Inc. J Graph Theory 44: 159–165, 2003

πŸ“œ SIMILAR VOLUMES

Short proofs for two theorems of Chien,
Short proofs for two theorems of Chien, Hell and Zhu
✍ Tracy Holt; Yared Nigussie πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 99 KB

In (J Graph Theory 33 (2000) , 14-24), Hell and Zhu proved that if a series-parallel graph G has girth at least 2 (3k -1) / 2 , then c (G) ≀ 4k / (2k -1). In (J Graph Theory 33 (2000), [185][186][187][188][189][190][191][192][193][194][195][196][197][198], Chien and Zhu proved that the girth condit

Boolos-style proofs of limitative theore
Boolos-style proofs of limitative theorems
✍ GyΓΆrgy SerΓ©ny πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 126 KB

## Abstract Boolos's proof of incompleteness is extended straightforwardly to yield simple β€œdiagonalization‐free” proofs of some classical limitative theorems of logic. (Β© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

A short proof of a theorem on Hamiltonia
A short proof of a theorem on Hamiltonian graphs
✍ Ainouche, A. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 219 KB πŸ‘ 2 views

In this note, w e give a short proof of a stronger version of the following theorem: Let G be a 2-connected graph of order n such that for any independent set {u, u , w}, then G is hamiltonian. 0 1996 John

A Short Proof of Mader's S-Paths Theorem
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 New Proof of a Classical Theorem in De
A New Proof of a Classical Theorem in Design Theory
✍ G.B. Khosrovshahi; B. Tayfeh-Rezaie πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 92 KB

We present a new proof of the well known theorem on the existence of signed (integral) t-designs due to Wilson and Graver and Jurkat.