๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A short proof of Kuratowski's graph planarity criterion

โœ Scribed by Makarychev, Yury

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
64 KB
Volume
25
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present a new short combinatorial proof of the sufficiency part of the well-known Kuratowski's graph planarity criterion. The main steps are to prove that for a minor minimal non-planar graph G and any edge xy:

(1) G-x-y does not contain ฮธ-subgraph;

(2) G-x-y is homeomorphic to the circle;

(3) G is either K 5 or K {3,3} .

๐Ÿ“œ SIMILAR VOLUMES

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 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.

Proof of a conjecture on cycles in a bip
Proof of a conjecture on cycles in a bipartite graph
โœ Wang, Hong ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 244 KB ๐Ÿ‘ 1 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k โ‰ฅ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n โ‰ฅ 3k, i.e., M (k) โ‰ค 3k. W