DMGT

AN INDUCTIVE PROOF OF WHITNEY'S BROKEN CIRCUIT THEOREM

Klaus Dohmen

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

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.

[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