Combinatorica
Volume 26, Number 3, 277-314, DOI: 10.1007/s00493-006-0017-y

Original Paper

Mader’s Conjecture On Extremely Critical Graphs

Matthias Kriesell

View Related Documents

Abstract

A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism).
Here we prove this conjecture.

Mathematics Subject Classification (2000):  05C40 - 05C35 - 05C75

Fulltext Preview

Image of the first page of the fulltext document