ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 141-151
From spanning forests to edge subsets
Martin Trinks *
Hochschule Mittweida, Faculty Mathematics / Sciences / Computer Science, Technikumplatz 17, 09648 Mittweida, Germany
Received 16 September 2011, accepted 13 February 2013, published online 8 April 2013
We give some insight into Tutte's definition of internally and externally active edges for spanning forests. Namely we prove, that every edge subset can be constructed from the edges of exactly one spanning forest by deleting a unique subset of the internally active edges and adding a unique subset of the externally active edges.
Keywords: Spanning forests, edge subsets, Tutte polynomial. Math. Subj. Class.: 05C30, 05C31
1 Introduction
The Tutte polynomial originally defined by a sum over spanning forests using (the number of) internally and externally active edges [12], can also be given as a sum over edge subsets [14, Equation (9.6.2)]. We show how both representations, as sum over spanning forests and as sum over edge subsets, are directly connected to each other.
Namely we prove, that every edge subset can be constructed from the edges of exactly one spanning forest by deleting a unique subset of the internally active edges and adding a unique subset of the externally active edges.
While seeking a generalization to matroids we observed that the statement is already given by Bjorner [4, Proposition 7.3.6]. It seems that this result is not well known in graph theory. Hence we state it explicitly in the special case of graphs and verify it graph-theoretically.
We apply this in some direct proofs for the equivalence of different representations of the Tutte polynomial, the chromatic polynomial, the reliability polynomial and the weighted graph polynomial.
Definition 1.1. A graph G = (V, E) is an ordered pair of a set V, the vertex set, and a multiset E, the edge set, such that the elements of the edge set are one- and two-element subsets of the vertex set, e G (1) U (2) for all e G E.
♦Supported by European Social Fond grant 080940498.
E-mail address: trinks@hs-mittweida.de (Martin Trinks)
Abstract
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
142
ArsMath. Contemp. 7 (2014) 123-140
For a graph G = (V, E), we denote the number of connected components of G by k(G) and refer to G with the edge e e E deleted and with the edge f e (1) U (2) added by G-e and G+f, respectively.
Definition 1.2. Let G = (V, E) be a graph and A C E an edge subset of G. A graph
G(A) = (V, A) is a spanning subgraph of G. A tree T = (V, A) is a spanning tree of G. A forest F = (V, A) is a spanning forest of G, if k(G) = k(F). The set of spanning trees and the set of spanning forests of the graph G are denoted by T (G) and F (G), respectively.
While the term "spanning tree" is unambiguous, the term "spanning forest" is not, because not every spanning subgraph, which is a forest, is a "spanning forest". A spanning forest is the union of spanning trees of each connected component.
In the following we consider graphs G = (V, E) with a linear order < on the edge set E. This linear order can be represented by a bijection fi: E ^ {1,..., |E|} for all e, f e E with
e < f ^ fi(e) <fi(f).	(1.1)
Definition 1.3 (Section 3 in [12]). Let G = (V, E) be a graph with a linear order < on the edge set E and F = (V, A) e F(G) a spanning forest of G. An edge e e A is internally active in F with respect to G and <, if there exists no edge f e E \ A, such that e < f and
F-e+ f e F (G). We denote the set of internally active edges and the number of internally active edges of F with respect to G and < by Ej(F, G, <) and i(F, G, <), respectively.
An edge e in the spanning forest F is internally active, if it is the maximal edge of all edges in the cut crossed by itself (connecting the vertices in the connected components arising by deleting e from F). In other words, the edge e can not be replaced by a greater edge (not in the spanning forest), such that F remains a spanning forest.
Definition 1.4 (Section 3 in [12]). Let G = (V, E) be a graph with a linear order < on the edge set E and F = (V, A) e F(G) a spanning forest of G. An edge f e E \ A is externally active in F with respect to G and <, if there exists no edge e e A, such that f < e and F-e+ f e F(G). We denote the set of externally active edges and the number of externally active edges of F with respect to G and < by Ee(F, G, <) and e(F, G, <), respectively.
An edge f not in the spanning forest is externally active, if it is the maximal edge of all edges in the cycle closed by itself. In other words, there is no greater edge (in the spanning forest), which can be replaced by f, such that F remains a spanning forest.
Definition 1.5 (Section 3 in [12]). Let G = (V, E) be a graph with a linear order < on the edge set E. The Tutte polynomial is defined as
T (G,x,y) = E xi(FG'<)ye(F'G'<).	(1.2)
F eF (G)
The primal usage of "a linear order on the edge set" seems to be by Whitney [18, Section 7]. Internally and externally active edges were probably first defined by Tutte [12, Section 3] to state the Tutte polynomial. This polynomial was originally introduced under the name "dichromate" for connected graphs [12, Equation (13)] and extended to
M. Trinks: From spanning forests to edge subsets
143
disconnected graphs by the multiplicativity with respect to components [12, Equation (18)]. It was shown, that the value of the polynomial is independent of the linear order on the edge set [12, page 85-88]. For some background to the definition of internally and externally active edges and the Tutte polynomial we refer to [1, 9, 15]. For surveys on the Tutte polynomial and its applications we refer to [5, 7, 11].
2 Main theorem
The spanning forests and their internally and externally active edges can be used to generate all edge subsets. We use the disjoint union U, the union of pairwise disjoint sets, in the statement of this main theorem below to indicate its bijectivity.
Theorem 2.1. Let G = (V, E) be a graph with a linear order < on the edge set E. Then U	U {(Af \ Ai) U Ae} = J {A} = 2E. (2.1)
F=(V,Af )£F(G) AiCEi(F,G,<)	ac_e
AeCEe(F,G,<)	c
Proof. We prove that the function m: {(Af ,Ai,Ae) | F = (V,Af) e F(G), Ai C Ei(F, G, <), Ae C Ee(F, G, <)} ^ 2E with m((Af ,Ai,Ae)) = (Af \ Ai) U Ae is a bijection.
First, we show that the function m is injective by an indirect proof. Assume it is not, that means there are two different triples A1 = (Af, Aj, Aj) and A2 = (A2, A2, A2), such that m(Aj) = m(A2) = A.
If A1 = A2, then Aj = A^, because otherwise Aj = Af \ A = Af \ A = A2 and Aj = A \ Aj = A \ Af = Ae and the triples would not be different.
As Ajj and Af are the edges of different spanning forests, there is an edge g e Ajj \ A2. Furthermore, for any choice of g, there is an edge h e Af \ Aj, such that (V, Aj)-g+h, (V, A2)-h+g e F(G). (There is at least one edge in the path connecting the incident vertices of g in (V, Af), which is in the cut crossed by g in (V, Aj). These conditions ensure that we can "compare" the edges g and h, because g is in the cycle closed by adding h to Aj and, equivalently, in the cut crossed by h in Af, and vice versa.)
We distinguish whether g (g e Af but g e Af) and h (h e Ajj but h e Af) are in A or
not:
•	Case 1: g e A, h e A: We have a contradiction by
-	geA ^ geAe ^ h<g,
-	he A ^ heAj ^ g<h.
•	Case 2: g e A, h e A: We have a contradiction by
-	geA ^ geAe ^ h<g,
-	heA ^ h e A2 ^ g < h.
•	Case 3: g e A, h e A: We have a contradiction by
-	geA ^ g e Aj ^ h<g,
-	heA ^ heAj ^ g<h.
144
ArsMath. Contemp. 7 (2014) 123-140
• Case 4: g £ A, h £ A: We have a contradiction by
-	g£A ^ g £ A1 ^ h < g,
-	h £ A ^ heA^ ^ g<h.
Consequently there are no such triples A1 and A2, hence the function m is injective. Second, we show that the function m is surjective by proving that for each edge set A C E there is a spanning forest F e F(G) and a triple (Af, Aj, Ae) with F = (V, Af), Aj C Ej(F,G, <),Ae C Ee(F,G,<) such that m((Af ,Aj,Ae)) = A.
We arrange the edges of A and E \ A in a sequence e1,...,e|E|, such that the edges of A appear before the edges of E \ A, that the edges of A are increasing, and that the edges of E \ A are decreasing, both with respect to <.
We start with the edgeless graph on the vertex set V and successively add the edges of E as they appear in the sequence to the graph, if the graph remains cycle-free. That means G0 = (V, 0) and for ie {1,..., |E|} we have
Gj f g;-i if G++e1 is a forest,
\ Gi-1 if G+Te1 is not a forest.
Thus, G|E| = F = (V, Af) e F(G) is a spanning forest of G.
An edge, which is in A but not in Af, is not added to Gj, meaning that it would close a cycle consisting of earlier added and thus lesser edges of A, hence this edge is an externally active edge (maximal edge of the cycles closed by itself), A \ Af = Ae C Ee(F, G, <).
An edge, which is not in A but in Af, is added to Gj, meaning that it is the first and thus greatest edges of E \ A crossing the according cut and hence this edge is an internally active edge (maximal edge of the cut crossed by itself), Af \ A = Aj C Ej(F, G, <).
Consequently, for each edge subset A C E there is a spanning forest F F(G) and an according triple (Af, Aj, Ae) with (Af \ Aj) U Ae = A, hence the function m is surjective.	□
Corollary 2.2. Let G = (V, E) be a graph with a linear order < on the edge set E, A C E an edge subset of G and f (G, A) a function mapping in a commutative semigroup. Then
£	£ f(G, A) = £ f(G, A).	(2.2)
F=(V,Af )eF(G) A=(Af\Ai)UAe	ACE
AiCEi(F,G,<)
AeCEe(F,G,<)
Proof. The equation follows directly from Theorem 2.1.	□
Corollary 2.3 (Theorem 3 in [7]). Let G = (V, E) be a graph with a linear order < on the edge set E. Then
£ 2i(F,G,<)+e(F,G,<) =2IE|.	(23)
F eF (G)
Proof. The equation follows directly from Corollary 2.2 with f (G, A) = 1.	□
M. Trinks: From spanning forests to edge subsets
145
To apply Theorem 2.1, the following lemma stating some kind of independence of the internally and externally active edges of a given spanning forest seems useful: Deleting an internally active edge splits a connected component, which can not be reconnected by adding externally active edges. Adding an externally active edge connects vertices already connected by a path, which can not be destroyed by deleting internally active edges.
Lemma 2.4. Let G = (V,E) be a graph with a linear order < on the edge set E and € F(G) a spanning forest of G. For all e € Ei(F,G, <) and f G Ee(F,G, <) it holds
k(F) = k(F+f) > k(F-e+f) = k(F-e) = k(F) - 1.	(2.4)
Proof. The first part, k(F) = k(F+f) > k(F-e) = k(F) - 1, follows directly from the definition of a spanning forest. The idea to prove the rest, k(F-e+f) = k(F-e), is already used in the case distinction in the proof of Theorem 2.1: The edge f can not reconnect the connected components arising from the deletion of e, because otherwise each of the two edges must be greater than the other.	□
3 Applications of the main theorem
As an application of Theorem 2.1 we prove the equivalence of representations using sums over spanning forests/trees (spanning forest/tree representation) and sums over edge subsets (edge subset representation) for the Tutte polynomial, the chromatic polynomial, the reliability polynomial and (a derivation of) the weighted graph polynomial.
3.1 Edge subset representation of the Tutte polynomial
The edge subset representation of the Tutte polynomial was first given by Tutte stating the relation to the dichromatic polynomial [13, Equation (21)]. In this article, the dichromatic polynomial is defined by an edge subset representation and it is shown, that it satisfies recurrence relations [13, Equations (18) - (20)] analogous to the recurrence relations satisfied by the Tutte polynomial [12, Equations (18) - (20)].
Theorem 3.1 (Equation (9.6.2) in [14]). Let G = (V, E) be a graph with a linear order < on the edge set E. The Tutte polynomial has the edge subset representation
T(G,x,y) = £ (x - l)k(G<A»-k(G)(y - 1 )|A|-|V|+k(G(A».	(3.1)
ACE
Proof. First, we expand the definition of the Tutte polynomial (Definition 1.5) using the binomial theorem:
T (G,x,y)= £ xi(F'G'<) ye(F'G'<)
F eF (G)
= £ (x - l + l)1 Ei(F,G,<) 1 (y - 1 + 1) 1 Ee(F,G,<) 1 F eF (G)
= £ £ (x - 1)^(y - 1)'A*'.
FeF(G) AiCEi(F,G,<)
AeCEe(F,G,<)
Second, we represent for each spanning forest F the number of internally and externally active edges in terms of the graph G and the spanning subgraph G(A) = (V, A) with
146
ArsMath. Contemp. 7 (2014) 123-140
A = (Af \ Ai) U Ae using Lemma 2.4: If G(A) has more connected components than the graph G, each "additional" connected component results from deleting an internally active edge, i.e., |Ai| = k(G(A)) — k(G). If G(A) is not a forest, each "additional" edge (closing a cycle) results from adding an externally active edge, i.e., |Ae| = |A| — |V| + k(G(A)). Thus we have
T (G,x,y)= £	£ (x — 1)|Ai| (y — 1)|Ae|
F=(V,Af )eF(G) A=(Af\A,)UAe AiCEi{F,G,<) AcCEe(F,G,<)
=	£	£ (x — 1)fc(G<A))-fc(G)(y — 1)|A|-|V | + fc(G<A».
F=(V,Af )eF(G) A=(Af\A,)UAe AiCEi(F,G,<) AsCEe(F,G,<)
Finally, the statement follows by Corollary 2.2:
T(G,x,y) = £ (x — i)k(G<A))-k(G)(y — i)|A|-|V|+k(G(A)).	n
ACE
3.2 Spanning forest representation of the chromatic polynomial
Definition 3.2 ([3]). Let G = (V, E) be a graph. The chromatic polynomial x(G, x) is the number of proper (vertex) colorings of G with at most x colors.
The spanning forest representation of the chromatic polynomial can be easily derived from its relation to the Tutte polynomial, which follows from the recurrence relations both polynomials satisfy. But the direct proof points out more clearly why internally and externally active edges make different contributions to the chromatic polynomial.
Theorem 3.3 (Theorem 14.1 in [2]). Let G = (V, E) be a graph with a linear order < on the edge set E. The chromatic polynomial has the spanning forest representation
x(G, x) = ( —1) | V |(—x)k(G) £ (1 — x)i(F,G,<).	(3.2)
f eF (G)
e(F,G,<)=0
Proof. We start with the representation of the chromatic polynomial as sum over edge subsets [17, Section 2] and apply Corollary 2.2:
x(G, x) = £ xfc(G<A))( —1)|A| ACE
= £	£ xfc(G<A))( — 1)|A|.
F=(V,Af )eF(G) A=(Af\Ai)UAe AiCEi(F,G,<) AeCEe(F,G,<)
First, we analyze the contribution of the externally active edges Ae C Ee(F, G, <) to the term xfc(G^A))( —1)|A|: Each externally active edge f e Ee(F,G, <) contributes (independently) the factor —1 if f e Ae (the number of connected components is not
M. Trinks: From spanning forests to edge subsets
147
influenced), and the factor 1 otherwise:
X(G,x)= £	£ xk(G(A'UAe))(-1)lA'UAel
F=(V,Af )eF(G) A'=Af\Ai AiÇEi(F,G,<) AeÇEe(F,G,<)
=	£	£ Xk(G<A'))(-l)|A'l(-l)|Ae|
F=(V,Af )EF(G) A'=Af\Ai AiÇEi(F,G,<) AeÇEe(F,G,<)
=	£	£ Xk(G<A'>)(-l)|A' 1	£	(-1)|A= 1
F=(V,AS )eF(G) A'=Af\Ai	Ae ÇES(F,G,<)
AiÇEi(F,G,<)
= £	£ xk(Gl^A">)(-1)|A'|(1 - 1)e(F,G<
F=(V,Af )EF(G) A'=Af\Ai AiÇEi(F,G,<)
= £	£ xk(G<A'»(-1)|A'L
F=(V,Af )eF(G) A'=Af\Ai e(F,G,<)=0 AiÇEi(F,G,<)
Second, we analyze the contribution of the internally active edges Ai ç Ei(F, G, <) to the term xk(Gl'A},)( — 1)\A^: Each internally active edge e G Ei(F,G, <) contributes (independently) the factor -x if e G Ai (the number of connected components is increased by 1), and the factor 1 otherwise:
x(G, x) = £	£ xk(GA\*»(-1)|Af\Ai|
F=(V,Af )eF(G) AiÇEi(F,G,<) e(F,G,<) = 0
£	£ x^'Af)-)^^-^ |AH(-1) A
F=(V,Af )eF(G) AiCEi(F,G,<) e(F,G,<) = 0
= £ xk(G)(-1)|V 1 -k(G) £ (-x) 1 A 1
FeF(G)	AiCEi(F,G,<)
e(F,G,<) = 0
= (-1)|Vl(-x)k(G) £ (1 - x)i(F,G,<).	□
F eF(G) e(F,G,<)=0
The proof above also "includes" the Broken-cycle Theorem [18, Section 7], [6, Theorem 2.3.1]: The edge subsets not including any broken cycle are exactly the edge subsets resulting from spanning forests having no externally active edges by deleting a subset of internally active edges. Hence the Broken-cycle Theorem can be stated as
x(G, x) = £	£ xk(G<A'))(-1)|A'1	(3.3)
F=(V,Af )eF(G) A'=Af\Ai e(F,G,<)=0 AiCEi(F,G,<)
= £	£ x|V|-|A'|(-1)|A'l	(3.4)
F=(V,Af )eF(G) A'=Af\Ai e(F,G,<)=0 AiCEi(F,G,<)
148
ArsMath. Contemp. 7 (2014) 123-140
The connection between the spanning forest representation and the Broken-cycle Theorem is also given in [1].
3.3 Spanning tree representation of the reliability polynomial
The set of connected spanning subgraphs of a connected graph can be enumerated from the spanning trees by only adding externally active edges. We apply this insight to obtain a spanning tree representation of the reliability polynomial.
For a statement S, let [S] equal 1, if S is true, and 0 otherwise [8].
Lemma 3.4 (Section 5, Item (19) in [16]). Let G = (V, E) be a graph with a linear order < on the edge set E. The generating function (in the indeterminant y) for the number of connected spanning subgraphs S(G, y) has the spanning tree representation
S(G,y)= £ [k(G{A)) = 1]y|A|	(3.5)
ACE
= ylV1-1 £ (1 + y)e(T'G'<).	(3.6)
T eT (G)
Proof. We start by applying Corollary 2.2:
S(G, y) = £ [k(G(A)) = 1]y|A|
ACE
= £	£ [k(G(A)) = 1]y|A|.
F=(V,Af )eF(G) A=(Af\A,)UAe AiCEi(F,G,<) AeCEe(F,G,<)
The spanning subgraph G(A) is connected only if the graph G is connected, that means the spanning forests are spanning trees with | V | — 1 edges, and if no (internally active) edge is deleted from the spanning tree. It follows:
S(G,y)= £	£ yIAI
T=(V,At)eT (G) A=AtUAe
AeCEe(T,G,<)
= £ £ yWyW
T=(V,At)eT(G) AeCEe(T,G,<)
= £ y|At 1 £ yIAe
T=(V,At)eT (G) AeCEe(T,G,<)
= y^1-1 £ (1 + y)e(TG'<).	□
T eT (G)
The probability, that all vertices of a graph are connected, if all edges of the graph are independently available with a probability p, is a polynomial in p, the reliability polynomial
R(G,p) [7, 16].
Definition 3.5. Let G = (V, E) be a graph. The reliability polynomial is defined as
R(G,p) = £ [k(G(A)) = 1] p|A|(1 — p)|E\A|.	(3.7)
ACE
M. Trinks: From spanning forests to edge subsets
149
Theorem 3.6 (Section 5, Item (15) in [16]). Let G = (V, E) be a graph with a linear order < on the edge set E. The reliability polynomial R(G,p) has the spanning tree representation
R(G,p) = (1 - p) 1 E 1 - 1 V 11 V 1 £ (1_ p)U,<). (3.8)
teT(G) k '
Proof. We rewrite the definition of the reliability polynomial using S(G,y):
R(G,p) = E [k(G(A)) = 1]p1A-p)1 E\A 1
ACE
I A |
E [k(G{A)) = i]f-P-) (1 -p) 1
ACE	^ - '
(1 -p) 1 E 1 S a,- p
i — p,
From this the statement follows directly by Lemma 3.4.	□
3.4 Spanning forest representation of a derivation of the weighted graph polynomial
For the graph polynomials above it was possible to derive a spanning forest/tree representation that depends only on the number of internally and externally active edges, independently of the corresponding edge sets. Obviously, this is not possible for every graph polynomial, also not for those having an edge subset representation.
The graph polynomial U'(G,x,y), a derivation of the weighted graph polynomial U(G,x,y) [10], is an example where only the contribution of the externally active edges can be summed up.
Definition 3.7. Let G = (V, E) be a graph and X = (x\,...,x | V |). The graph polynomial
U'(G, x, y) is defined as
U '(a, X, y) = EÖ Xfci(G(A>VA',	(3.9)
ACEi=l
where ki(G) denotes the number of connected components including exactly i vertices.
Theorem 3.8. Let G = (V, E) be a graph with a linear order < on the edge set E and X = (xi,... ,X'V'). The (derivation of the) weighted graph polynomial U '(a, X, y) has the spanning forest representation
U '(a, X, y) = E	E n x^(G{A))y' A'(1+ y)e(F'G'<), (3.10)
F=(V,Af )£F(G) A=Af\Ai i=l AiCEi(F,G,<)
where ki (G) denotes the number of connected components including exactly i vertices.
E
150
ArsMath. Contemp. 7 (2014) 123-140
Proof. We start by applying Corollary 2.2 and then sum up the contribution of the externally active edges (as in the proofs above):
U '(G,x,y)= £][[ x?(G<A» y|A|
ACE i=1
= e e in x^a>va|
F =(V,Af )eF(G) A=(Af\Ai)UAe i=1 Ai C Ei(F,G,<) Ae CEe(F,G,<)
= E E IIxki(G<A>)y|A|(1+ y)e(F,G,<). □
F=(V,Af )eF(G) A=Af\Ai i= 1 AiCEi(F,G,<)
References
[1]	R. A. Bari, Chromatic polynomials and the internal and external activities of Tutte, in: J. A. Bondy and U. S. R. Murty (eds.), Graph Theory and Related Topics, Academic Press, London, 1979, pp. 41-52, Proceedings of the conference held in honour of Professor W. T. Tutte on the occasion of his sixtieth birthday, University of Waterloo, July 5-9, 1977.
[2]	N. L. Biggs, Algebraic graph theory, volume 2, Cambridge University Press, Cambridge, 1993.
[3]	G. D. Birkhoff, A determinant formula for the number of ways of coloring a map. The Annals of Mathematics, 14 (1912), 42-46, 1912, JSTOR:1967597.6.
[4]	A. Bjorner, Homology and shellability of matroids and geometric lattices, in: N. White (ed.), Matroid Applications, volume 40 of Encyclopedia of mathematics and its applications, chapter 7, Cambridge University Press, Cambridge, 1992, pp. 226-283, doi:10.1017/ CBO9780511662041.008.
[5]	T. H. Brylawski and J. G. Oxley, The Tutte polynomial and its applications, in: N. White (ed.), Matroid Applications, volume 40 of Encyclopedia of mathematics and its applications, chapter 6, Cambridge University Press, Cambridge, 1992, pp. 123-225, doi:10.1017/ CBO9780511662041.007.
[6]	F. M. Dong, K. M. Koh and K. L. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific Publishing, 2005.
[7]	J. A. Ellis-Monaghan and C. Merino, Graph polynomials and their applications I: The Tutte polynomial, in: Matthias Dehmer (ed.), Structural Analysis of Complex Networks, chapter 9, Birkhauser, Boston, 2011, pp. 219-255, doi:10.1007/978-0-8176-4789-6_9.
[8]	D. E. Knuth, Two notes on notation, May 1992, arXiv:math/9205211v1.
[9]	J. P. S. Kung, Preface: Old and new perspectives on the Tutte polynomial, Annals of Combinatorics 12 (2008), 133-137, doi:10.1007/s0002 6-008-0342-5.
[10]	S. D. Noble and D. J. A. Welsh, A weighted graph polynomial from chromatic invariants of knots, Annales de l'institut Fourier 49 (1999), 1057-1087, http://aif.cedram.org/ item?id=AIF_19 99_4 9_3_105 7_0.
[11]	A. D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, in: Surveys in combinatorics, volume 327, 2005, pp. 173-226, doi:10.1017/
CBO9780511734885.009.
M. Trinks: From spanning forests to edge subsets
151
[12]	W. T. Tutte, A contribution to the theory of chromatic polynomials, Canadian Journal of Mathematics 6 (1954), 80-91, doi:10.4153/CJM-1954-010-9.
[13]	W. T. Tutte, On dichromatic polynomials, Journal of Combinatorial Theory, 2 (1967), 301320, doi:10.1016/S0021-9800(67)80032-2.
[14]	W. T. Tutte, Graph Theory, volume 21 of Encyclopedia of mathematics and its applications, Cambridge University Press, Cambridge, 2001.
[15]	W. T. Tutte, Graph-polynomials, Advances in Applied Mathematics 32 (2004), 5-9, doi:10. 1016/S0196-8858(03)00041-1.
[16]	D. J. A. Welsh and C. Merino, The Potts model and the Tutte polynomial, Journal of Mathematical Physics 41 (2000), 1127-1152, doi:10.1063/1.533181.
[17]	H. Whitney, The coloring of graphs, Proceedings of the National Acadamy of Sciences of the USA, 17 (1931), 122-125, http://www.ncbi.nlm.nih.gov/pmc/articles/ PMC1076007.
[18]	H. Whitney, A logical expansion in mathematics, Bulletin of the American Mathematical Society 38 (1932), 572-579, http://projecteuclid.org/euclid.bams/ 1183496087.