Discussiones Mathematicae Graph Theory 31(3) (2011) 577-586
doi: 10.7151/dmgt.1561

[BIBTex] [PDF] [PS]

AN INDUCTIVE PROOF OF WHITNEY'S BROKEN CIRCUIT THEOREM

Klaus Dohmen

Hochschule Mittweida
Technikumplatz 17
09648 Mittweida, Germany
e-mail: dohmen@hs-mittweida.de

Abstract

We present a new proof of Whitney's broken circuit theorem based on induction on the number of edges and the deletion-contraction formula.

Keywords: chromatic polynomial, broken circuit, induction.

2010 Mathematics Subject Classification: Primary: 05C15;
Secondary: 05A15.

References

[1] G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. Math. 14 (1912) 42-46, doi: 10.2307/1967597.
[2] N. Biggs, Algebraic Graph Theory, 2nd edition, (Cambridge University Press, 1994).
[3] A. Blass and B.E. Sagan, Bijective proofs of two broken circuit theorems, J. Graph Theory 10 (1986) 15-21, doi: 10.1002/jgt.3190100104.
[4] K. Dohmen, An improvement of the inclusion-exclusion principle, Arch. Math. 72 (1999) 298-303, doi: 10.1007/s000130050336.
[5] R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52-71, doi: 10.1016/S0021-9800(68)80087-0.
[6] H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932) 572-579, doi: 10.1090/S0002-9904-1932-05460-X.

Received 10 December 2009
Revised 3 August 2010
Accepted 3 August 2010