# An Algebraic Representation of Graphs and Applications to Graph Enumeration

Authors: Ângela Mestre
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

We give a recursion formula to generate all the equivalence classes of connected graphs with coefficients given by the inverses of the orders of their groups of automorphisms. We use an algebraic graph representation to apply the result to the enumeration of connected graphs, all of whose biconnected components have the same number of vertices and edges. The proof uses Abel’s binomial theorem and generalizes Dziobek’s induction proof of Cayley’s formula.


---

## Body

## 1. Introduction

As pointed out in [1], generating graphs may be useful for numerous reasons. These include giving more insight into enumerative problems or the study of some properties of graphs. Problems of graph generation may also suggest conjectures or point out counterexamples. The use of generating functions (or functionals) in the enumeration or generation of graphs is standard practice both in mathematics and physics [2–4]. However, this is by no means obligatory since any method of manipulating graphs may be used.Furthermore, the problem of generating graphs taking into account their symmetries was considered as early as the 19th century [5] and more recently for instance, in [6]. In particular, in quantum field theory, generated graphs are weighted by scalars given by the inverses of the orders of their groups of automorphisms [4]. In [7, 8], this was handled for trees and connected multigraphs (with multiple edges and loops allowed), on the level of the symmetric algebra on the vector space of time-ordered field operators. The underlying structure is an algebraic graph representation subsequently developed in [9]. In this representation, graphs are associated with tensors whose indices correspond to the vertex numbers. In the former papers, this made it possible to derive recursion formulas to produce larger graphs from smaller ones by increasing by 1 the number of their vertices or the number of their edges. An interesting property of these formulas is that of satisfying alternative recurrences which relate either a tree or connected multigraph on n vertices with all pairs of their connected subgraphs with total number of vertices equal to n. In the case of trees, the algorithmic description of the corresponding formula is about the same as that used by Dziobek in his induction proof of Cayley’s formula [10, 11]. Accordingly, the formula induces a recurrence for nn-2/n!, that is, the sum of the inverses of the orders of the groups of automorphisms of all the equivalence classes of trees on n vertices [12, page 209].For simplicity, here bygraphs we mean simple graphs. However, our results generalize straightforwardly to graphs with multiple edges allowed. One instance of an algorithm for finding the biconnected components of a connected graph is given in [13]. Our goal here is rather to generate all the equivalence classes of connected graphs so that they are decomposed into their biconnected components and have the coefficients announced in the abstract. To this end, we give a suitable graph transformation to produce larger connected graphs from smaller ones by increasing the number of their biconnected components by one unit. This mapping is then used to extend the recurrence of [7] to connected graphs. This new recurrence decomposes the graphs into their biconnected components and, in addition, can be generalized to restricted classes of connected graphs with specified biconnected components. The proof proceeds as suggested in [7]. That is, given an arbitrary equivalence class whose representative is a graph on m edges, say, G, we show that every one of the m edges of the graph G adds 1/(m·|autG|) to the coefficient of G. To this end, we use the fact that labeled vertices are held fixed under any automorphism.Moreover, in the algebraic representation framework, the result yields a recurrence to generate linear combinations of tensors over the rational numbers. Each tensor represents a connected graph. As required, these linear combinations have the property that the sum of the coefficients of all the tensors representing isomorphic graphs is the inverse of the order of their group of automorphisms. In this context, tensors representing generated graphs are factorized into tensors representing their biconnected components. As in [7–9], a key feature of this result is its close relation to the algorithmic description of the computations involved. Indeed, it is easy to read off from this scheme not only algorithms to perform the computations, but even data structures relevant for an implementation.Furthermore, we prove that when we only consider the restricted class of connected graphs whose biconnected components all have, say,p vertices and r edges, the corresponding recurrence has an alternative expression which relates connected graphs on μ biconnected components with all the p-tuples of their connected subgraphs with total number of biconnected components equal to μ-1. This induces a recurrence for the sum of the inverses of the orders of the groups of automorphisms of all the equivalence classes of connected graphs on μ biconnected components with that property. The proof uses an identity related to Abel’s binomial theorem [14, 15] and generalizes Dziobek’s induction proof of Cayley’s formula [10].This paper is organized as follows. Section2 reviews the basic concepts of graph theory underlying much of the paper. Section 3 contains the definitions of the elementary graph transformations to be used in the following. Section 4 gives a recursion formula for generating all the equivalence classes of connected graphs in terms of their biconnected components. Sections 5 and 6 review the algebraic representation and some of the linear mappings introduced in [7, 9]. Section 7 derives an algebraic expression for the recurrence of Section 4 and for the particular case in which graphs are such that their biconnected components are all graphs on the same vertex and edge numbers. An alternative formulation for the latter is also given. Finally, Section 8 proves a Cayley-type formula for graphs of that kind.


## 2. Basics

We briefly review the basic concepts of graph theory that are relevant for the following sections. More details may be found in any standard textbook on graph theory such as [16].LetA and B denote sets. By [A]2 we denote the set of all the 2-element subsets of A. Also, by 2A we denote the power set of A, that is, the set of all the subsets of A. By card A we denote the cardinality of the set A. Furthermore, we recall that the symmetric difference of the sets A and B is given by AΔB:=(A∪B)∖(A∩B).Here, agraph is a pair G=(V,E), where V⊂ℕ is a finite set and E⊆[V]2. Thus, the elements of E are 2-element subsets of V. The elements of V and E are called vertices and edges, respectively. In the following, the vertex set of a graph G will often be referred to as V(G), the edge set as E(G). The cardinality of V(G) is called the order of G, written as |G|. A vertex v is said to be incident with an edge e if v∈e. Then, e is an edge atv. The two vertices incident with an edge are its endvertices. Moreover, the degree of a vertex v is the number of edges at v. Two vertices v and u are said to be adjacent if {v,u}∈E. If all the vertices of G are pairwise adjacent, then G is said to be complete. A graph G* is called a subgraph of a graph G if V(G*)⊆V(G) and E(G*)⊆E(G). A path is a graph P on n≥2 vertices such that E(P)={{v1,v2},{v2,v3},…,{vn-1,vn}},  vj∈V(P) for all j=1,…,n. The vertices v1 and vn have degree 1, while the vertices v2,…,vn-1 have degree 2. In this context, the vertices v1 and vn are linked by P and called the endpoint vertices. The vertices v2,…,vn-1 are called the inner vertices. A cycle is a graph C on n>2 vertices such that E(C)={{v1,v2},{v2,v3},…,{vn-1,vn},{vn,v1}}, vj∈V(C) for all j=1,…,n, every vertex having degree 2. A graph is said to be connected if every pair of vertices is linked by a path. Otherwise, it is disconnected. Given a graph G, a maximal connected subgraph of G is called a component of G. Furthermore, given a connected graph, a vertex whose removal (together with its incident edges) disconnects the graph is called a cutvertex. A graph that remains connected after erasing any vertex (together with incident edges) (resp. any edge) is said to be 2-connected (resp. 2-edge connected). A 2-connected graph (resp. 2-edge connected graph) is also called biconnected (resp. edge-biconnected). Given a connected graph H, a biconnected component of H is a maximal subset of edges such that the induced subgraph is biconnected (see [17, Section 6.4] for instance). Here, we consider that an isolated vertex is, by convention, a biconnected graph with no biconnected components.Moreover, given a graphG, the set 2E(G) is a vector space over the field ℤ2 such that vector addition is given by the symmetric difference. The cycle space𝒞(G) of the graph G is defined as the subspace of 2E(G) generated by all the cycles in G. The dimension of 𝒞(G) is called the cyclomatic number of the graph G. We recall that dim𝒞(G)=cardE(G)-|G|+c, where c denotes the number of connected components of the graph G [18].We now introduce a definition of labeled graph. LetL be a finite set. Here, a labeling of a graph G is a mapping l:V(G)→2L such that ∪v∈V(G)l(v)=L and l(v)∩l(v′)=∅ for all v,v′∈V(G) with v≠v′. In this context, L is called a label set, while the graph G is said to be labeled withL or simply a labeled graph. In the sequel, a labeling of a graph G will be referred to as lG. Moreover, an unlabeled graph is one labeled with the empty set.Furthermore, anisomorphism between two graphs G and G* is a bijection φ:V(G)→V(G*) which satisfies the following conditions: (i)
{v,v′}∈E(G) if and only if {φ(v),φ(v′)}∈E(G*),(ii)
L∩lG(v)=L∩lG*(φ(v)). Clearly, an isomorphism defines an equivalence relation on graphs. In particular, an isomorphism of a graph G onto itself is called an automorphism (or symmetry) of G.


## 3. Elementary Graph Transformations

We introduce the basic graph transformations to change the number of biconnected components of a connected graph by one unit.Here, given an arbitrary setX, let ℚX denote the free vector space on the set X over ℚ, the set of rational numbers. Also, for all integers n≥1 and k≥0 and label sets L, let
(1)Vn,k,L={∫G:|G|=n,dim𝒞(G)=k,GislabeledbylG:V(G)→2L∫}.
Furthermore, let(i)
Vconnn,k,L={G∈Vn,k,L:Gisconnected},(ii)
Vbiconnn,k,L={G∈Vn,k,L:Gisbiconnected}. In what follows, when L=∅ we will omit L from the upper indices in the previous definitions.We proceed to the definition of the elementary linear mappings to be used in the following. Note that, for simplicity, our notation does not distinguish between two mappings defined both according to one of the following definitions, one onVn,k,L and the other on Vp,q,L′ with n≠p or k≠q or L≠L′. This convention will often be used in the rest of the paper for all the mappings given in this section. Therefore, we will specify the domain of the mappings whenever confusion may arise. (i)
Adding a biconnected component to a connected graph: let L be a label set. Let G be a graph in Vconnn,k,L. Let V(G)={vi}i=1,…,n. For all i=1,…,n, let 𝒦i denote the set of biconnected components of G such that vi∈V(H) for all H∈𝒦i. Let ℒ denote the set of all the ordered partitions of the set 𝒦i into p disjoint sets: ℒ={zi:=(𝒦i(1),…,𝒦i(p)):∪l=1p𝒦i(l)=𝒦iand𝒦i(l)∩𝒦i(l′)=∅∀l,l′=1,…,  pwithl≠l′}. Furthermore, let 𝒥 denote the set of all the ordered partitions of the set lG(vi) into p disjoint sets: 𝒥={wi:=(lG(vi)(1),…,lG(vi)(p)):∪l=1plG(vi)(l)=lG(vi)andlG(vi)(l)∩lG(vi)(l′)=∅∀l,l′=1,…,pwithl≠l′}. Finally, let G^ be a graph in Vbiconnp,q such that V(G)∩V(G^)=∅. (In case the graph G^ does not satisfy that property, we consider a graph G′ instead such that G′≅G^ and V(G)∩V(G′)=∅. We will not point this out explicitly in the following.) Let V(G^)={ul}l=1,…,p. In this context, for all i=1,…,n, define
(2)riG^:ℚVconnn,k,L→ℚVconnn+p-1,k+q,LG↦∑zi∈ℒ;wi∈𝒥‍Gwizi,where the graphsGwizi satisfy the following:
(a)
V(Gwizi)=V(G)∖{vi}∪V(G^),(b)
E(Gwizi)=E(G^)∪{{x,y}∈E(G):vi∉{x,y}}(3)⋃l=1p{{x,ul}:{x,vi}∈E(G),x∈∪H*∈𝒦i(l)V(H*)},(c)
lGwizi|V(G)∖{vi}=lG|V(G)∖{vi} and lGwizi(ul)=lG(vi)(l) for all l=1,…,p.The mappingsriG^ are extended to all of ℚVconnn,k,L by linearity. For instance, Figure 1 shows the result of applying the mapping riC4 to the cutvertex of a 2-edge connected graph with two biconnected components, where C4 denotes a cycle on four vertices.Furthermore, letX⊆Vbiconnp,q. Given a linear combination of graphs ϑ=∑G∈X‍αGG, where αG∈ℚ, we define
(4)riϑ:=∑G∈X‍αGriG.We proceed to generalize the edge contraction operation given in [16] to the operation of contracting a biconnected component of a connected graph.(ii)
Contracting a biconnected component of a connected graph: let L be a label set. Let G be a graph in Vconnn,k,L. Let G^∈Vbiconnp,q,L′ be a biconnected component of G, where L′=∪v∈V(G^)lG(v). Define
(5)cG^:Vconnn,k,L→Vconnn-p+1,k-q,L;G↦G*,Figure 1
The linear combination of graphs obtained by applying the mappingriC4 to the cutvertex of the graph consisting of two triangles sharing one vertex.where the graphG* satisfies the following:
(a)
V
(
G
*
)
=
V
(
G
)
∖
V
(
G
^
)
∪
{
v
}, where v:=min{v′∈ℕ:v′∉V(G)∖V(G^)},
(b)
E
(
G
*
)
=
{
{
x
,
y
}
∈
E
(
G
)
:
{
x
,
y
}
∩
E
(
G
^
)
=
∅
}
(6)
∪
{
{
x
,
v
}
:
{
x
,
y
}
∈
E
(
G
)
∖
E
(
G
^
)
and
y
∈
V
(
G
^
)
}
,
(c)
l
G
*
|
V
(
G
)
∖
V
(
G
^
)
=
l
G
|
V
(
G
)
∖
V
(
G
^
) and lG*(v)=∪u∈V(G^)lG(u).
For instance, Figure2 shows the result of applying the mapping cC4 to a 2-edge connected graph with three biconnected components.
We now introduce the following auxiliary mapping.
LetL be a label set. Let G be a graph in Vn,k,L. Let V(G)={vi}i=1,…,n. Let L′ be a label set such that L∩L′=∅. Also, let ℐ denote the set of all the ordered partitions of the set L′ into n disjoint sets: ℐ={y:=(L′(1),…,L′(n)):∪j=1nL′(j)=L′andL′(i)∩L′(j)=∅∀i,j=1,…,nwithi≠j}. In this context, define
(7)ξL′:ℚVn,k,L→ℚVn,k,L∪L′;G↦∑y∈ℐ‍Gy,
where the graphsGy satisfy the following:
(a)
V
(
G
y
)
=
V
(
G
),
(b)
E
(
G
y
)
=
E
(
G
),
(c)
l
G
y
(
v
i
)
=
l
G
(
v
i
)
∪
L
′
(
i
) for all i=1,…,n and vi∈V(G).
The mappingξL′ is extended to all of ℚVn,k,L by linearity.Figure 2
The graph obtained by applying the mappingcC4 to a graph with three biconnected components.


## 4. Generating Connected Graphs

We give a recursion formula to generate all the equivalence classes of connected graphs. The formula depends on the vertex and cyclomatic numbers and produces larger graphs from smaller ones by increasing the number of their biconnected components by one unit. Here, graphs having the same parameters are algebraically represented by linear combinations over coefficients from the rational numbers. The key feature is that the sum of the coefficients of all the graphs in the same equivalence class is given by the inverse of the order of their group of automorphisms. Moreover, the generated graphs are automatically decomposed into their biconnected components.In the rest of the paper, we often use the following notation: given a groupH, by |H| we denote the order of H. Given a graph G, by autG we denote the group of automorphisms of G. Accordingly, given an equivalence class 𝒜, by aut𝒜 we denote the group of automorphisms of all the graphs in 𝒜. Furthermore, given a set W⊆Vn,k,L, by ℰ(W) we denote the set of equivalence classes of all the graphs in W.We proceed to generalize the recursion formula for generating trees given in [7] to arbitrary connected graphs.Theorem 1.
For allp>1 and q≥0 suppose that βbiconnp,q:=∑G′∈Vbiconnp,q‍σG′G′ with σG′∈ℚ, is such that for any equivalence class 𝒜∈ℰ(Vbiconnp,q) the following holds: (i) there exists G′∈𝒜 such that σG′>0, (ii) ∑G′∈𝒜‍σG′=1/|aut𝒜|. In this context, given a label set L, for all n≥1 and k≥0, define βconnn,k,L∈ℚVconnn,k,L by the following recursion relation:
(8)βconn1,0,L∶=G,whereG=({1},∅),lG(1)=L,βconn1,k,L∶=0ifk>0,βconnn,k,L∶=1k+n-1×∑q=0k‍∑p=2n‍∑i=1n-p+1‍((q+p-1)riβbiconnp,q(βconnn-p+1,k-q,L)).
Then, βconnn,k,L=∑G∈Vconnn,k,L‍αGG with αG∈ℚ. Moreover, for any equivalence class 𝒞∈ℰ(Vconnn,k,L), the following holds: (i) there exists G∈𝒞 such that αG>0, (ii) ∑G∈𝒞‍αG=1/|aut𝒞|.Proof.
The proof is very analogous to the one given in [7] (see also [8, 19]).Lemma 2.
Letn≥1 and k≥0 be fixed integers. Let L be a label set. Let βconnn,k,L=∑G∈Vconnn,k,L‍αGG be defined by formula (8). Let 𝒞∈ℰ(Vconnn,k,L) denote any equivalence class. Then, there exists G∈𝒞 such that αG>0.Proof.
The proof proceeds by induction on the number of biconnected componentsμ. Clearly, the statement is true for μ=0. We assume the statement to hold for all the equivalence classes in ℰ(Vconnn-p+1,k-q,L) with p=2,…,n-1 and q=0,…,k, whose elements have μ-1 biconnected components. Now, suppose that the elements of 𝒞∈ℰ(Vconnn,k,L) have μ biconnected components. Let βbiconnp,q=∑G′∈Vbiconnp,q‍σG′G′ with σG′∈ℚ. Recall that by (4) the mappings riβbiconnp,q read as
(9)riβbiconnp,q:=∑G′∈Vbiconnp,q‍σG′riG′.
Let G denote any graph in 𝒞. We proceed to show that a graph isomorphic to G is generated by applying the mappings riβbiconnp,q to a graph G*∈Vconnn-p+1,k-q,L with μ-1 biconnected components and such that νG*>0, where νG* is the coefficient of G* in βconnn-p+1,k-q,L. Let G^∈Vbiconnp,q,L′ be any biconnected component of the graph G, where L′=∪v∈V(G^)lG(v). Contracting the graph G^ to the vertex u:=min{u′∈ℕ:u′∉V(G)∖V(G^)} yields a graph cG^(G)∈Vconnn-p+1,k-q,L with μ-1 biconnected components. Let 𝒟∈ℰ(Vconnn-p+1,k-q,L) denote the equivalence class such that cG^(G)∈𝒟. By the inductive assumption, there exists a graph H*∈𝒟 such that H*≅cG^(G) and νH*>0. Let vj∈V(H*) be the vertex mapped to u of cG^(G) by an isomorphism. Relabeling the graph G^ with the empty set yields a graph G′∈Vbiconnp,q. Applying the mapping rjG′ to the graph H* yields a linear combination of graphs, one of which is isomorphic to G. That is, there exists H≅G such that αH>0.Lemma 3.
Letn≥1 and k≥0 be fixed integers. Let L be a label set such that cardL≥n. Let βconnn,k,L=∑G∈Vconnn,k,L‍αGG be defined by formula (8). Let 𝒞∈ℰ(Vconnn,k,L) be an equivalence class such that lG(v)≠∅ for all v∈V(G) and G∈𝒞. Then, ∑G∈𝒞αG=1.Proof.
The proof proceeds by induction on the number of biconnected componentsμ. Clearly, the statement is true for μ=0. We assume the statement to hold for all the equivalence classes in ℰ(Vconnn-p+1,k-q,L) with p=2,…,n-1 and q=0,…,k, whose elements have μ-1 biconnected components and the property that no vertex is labeled with the empty set. Now, suppose that the elements of 𝒞∈ℰ(Vconnn,k,L) have μ biconnected components. By Lemma 2, there exists a graph G∈𝒞 such that αG>0, where αG is the coefficient of G in βconnn,k,L. Let m:=cardE(G). Therefore, m=k+n-1. By assumption, lG(v)≠∅ for all v∈V(G) so that |aut𝒞|=1. We proceed to show that ∑G∈𝒞‍αG=1. To this end, we check from which graphs with μ-1 biconnected components, the elements of 𝒞 are generated by the recursion formula (8), and how many times they are generated.
Choose any one of theμ biconnected components of the graph G∈𝒞. Let this be the graph G^∈Vbiconnp,q,L′, where L′=∪v∈V(G^)lG(v). Let m′:=cardE(G^) so that m′=q+p-1. Contracting the graph G^ to the vertex u with u:=min{u′∈ℕ:u′∉V(G)∖V(G^)} yields a graph cG^(G)∈Vconnn-p+1,k-q,L with μ-1 biconnected components. Let 𝒟∈ℰ(Vconnn-p+1,k-q,L) denote the equivalence class containing cG^(G). Since lcG^(G)(v)≠∅ for all v∈V(cG^(G)), we also have |aut𝒟|=1. Let βconnn-p+1,k-q,L=∑G*∈Vconnn-p+1,k-q,L‍νG*G* with νG*∈ℚ. By Lemma 2, there exists a graph H∈𝒟 such that H≅cG^(G) and νH>0. By the inductive assumption, ∑G*∈𝒟‍νG*=1. Now, let vj∈V(H) be the vertex which is mapped to u of cG^(G) by an isomorphism. Let G′∈Vbiconnp,q be the biconnected graph obtained by relabeling G^ with the empty set. Also, let 𝒜∈ℰ(Vbiconnp,q) denote the equivalence class such that G′∈𝒜. Apply the mapping rjG′ to the graph H. Note that every one of the graphs in the linear combination rjG′(H) corresponds to a way of labeling the graph G′ with lcG^(G)(u)=L′. Therefore, there are |aut𝒜| graphs in rjG′(H) which are isomorphic to the graph G. Since none of the vertices of the graph H is labeled with the empty set, the mapping rjG′ produces a graph isomorphic to G from the graph H with coefficient αG*=νH>0. Now, formula (8) prescribes to apply the mappings riG′ to the vertex which is mapped to u by an isomorphism of every graph in the equivalence class 𝒟 occurring in βconnn-p+1,k-q,L (with non-zero coefficient). Therefore,
(10)∑G∈𝒞‍αG*=|aut𝒜|·∑G*∈𝒟‍νG*=|aut𝒜|,
where the factor |aut𝒜| on the right hand side of the first equality is due to the fact that every graph in the equivalence class 𝒟 generates |aut𝒜| graphs in 𝒞. Hence, according to formulas (8) and (4), the contribution to ∑G∈𝒞‍αG is m′/m. Distributing this factor between the m′ edges of the graph G^ yields 1/m for each edge. Repeating the same argument for every biconnected component of the graph G proves that every one of the m edges of the graph G adds 1/m to ∑G∈𝒞‍αG. Hence, the overall contribution is exactly 1. This completes the proof.We now show thatβconnn,k,L satisfies the following property.Lemma 4.
Letn≥1 and k≥0 be fixed integers. Let L and L′ be label sets such that L∩L′=∅. Then, βconnn,k,L∪L′=ξL′(βconnn,k,L).Proof.
LetξL′:Vn,k,L→Vn,k,L∪L′ and ξ~L′:Vn-p+1,k-q,L→Vn-p+1,k-q,L∪L′ be defined as in Section 3. The identity follows by noting that ξL′∘riβbiconnp,q=riβbiconnp,q∘ξ~L′.Lemma 5.
Letn≥1 and k≥0 be fixed integers. Let L be a label set. Let βconnn,k,L=∑G∈Vconnn,k,LαGG be defined by formula (8). Let 𝒞∈ℰ(Vconnn,k,L) denote any equivalence class. Then, ∑G∈𝒞‍αG=1/|aut(𝒞)|.Proof.
LetG be a graph in 𝒞. If lG(v)≠∅ for all v∈V(G), we simply recall Lemma 3. Thus, we may assume that there exists a set V′⊆V(G) such that lG(V′)={∅}. Let L′ be a label set such that L∩L′=∅ and cardL′=cardV′. Relabeling the graph G with L∪L′ via the mapping l:V(G)→2L∪L′ such that l|V(G)∖V′=lG|V(G)∖V′ and l(v)≠∅ for all v∈V′ yields a graph G′∈Vconnn,k,L∪L′ such that |autG′|=1. Let 𝒟∈ℰ(Vconnn,k,L∪L′) be the equivalence class such that G′∈𝒟. Let βconnn,k,L∪L′=∑G′∈Vconnn,k,L∪L′‍νG′G′ with νG′∈ℚ. By Lemma 3, ∑G′∈𝒟‍νG′=1. Suppose now that there are exactly T distinct labelings lj:V(G)→2L∪L′,  j=1,…,T such that lj|V(G)∖V′=lG|V(G)∖V′, lj(v)≠∅ for all v∈V′, and Gj∈𝒟, where Gj is the graph obtained by relabeling G with lj. Clearly, νGj=αG>0, where νGj is the coefficient of Gj in βconnn,k,L∪L′. Define fj:G↦Gj for all j=1,…,T. Now, repeating the same procedure for every graph in 𝒞 and recalling Lemma 4, we obtain
(11)∑G′∈𝒟‍νG′=∑j=1T‍∑G∈𝒞‍νfj(G)=T∑G∈𝒞‍αG=1.
That is, ∑G∈𝒞‍αG=1/T. Since |aut𝒞|=T, we obtain ∑G∈𝒞‍αG=1/|aut(𝒞)|.
This completes the proof of Theorem1.Figure3 shows βconnn,k for 1≤n+k≤5. Now, given a connected graph G, let 𝒱G denote the set of biconnected components of G. Given a set X⊂∪p=2n∪q=0kVbiconnp,q, let VXn,k:={G∈Vconnn,k:ℰ(𝒱G)⊆ℰ(X)} with the convention VX1,0:={({1},∅)}. With this notation, Theorem 1 specializes straightforwardly to graphs with specified biconnected components.Figure 3
The result of computing all the pairwise non-isomorphic connected graphs as contributions toβconnn,k via formula (8) up to order n+k≤5. The coefficients in front of graphs are the inverses of the orders of their groups of automorphisms.Corollary 6.
For allp>1 and q≥0 suppose that γbiconnp,q:=∑G′∈Xp,q‍σG′G′ with σG′∈ℚ and Xp,q⊆Vbiconnp,q, is such that for any equivalence class 𝒜∈ℰ(Xp,q), the following holds: (i) there exists G′∈𝒜 such that σG′>0, (ii) ∑G′∈𝒜‍σG′=1/|aut𝒜|. In this context, for all n≥1 and k≥0, define γconnn,k∈ℚVconnn,k by the following recursion relation:
(12)γconn1,0∶=G,whereG=({1},∅),γconn1,k∶=0ifk>0,γconnn,k∶=1k+n-1×∑q=0k‍∑p=2n‍∑i=1n-p+1‍((q+p-1)riγbiconnp,q(γconnn-p+1,k-q)).
Then, γconnn,k=∑G∈VXn,k‍αGG, where αG∈ℚ and X:=∪p=2n∪q=0kXp,q. Moreover, for any equivalence class 𝒞∈ℰ(VXn,k) the following holds: (i) there exists G∈𝒞 such that αG>0 (ii) ∑G∈𝒞‍αG=1/|aut𝒞|.Proof.
The result follows from the linearity of the mappingsriG and the fact that larger graphs whose biconnected components are all in X can only be produced from smaller ones with the same property.


## 5. Algebraic Representation of Graphs

We represent graphs by tensors whose indices correspond to the vertex numbers. Our description is essentially that of [7, 9]. From the present section on, we will only consider unlabeled graphs.LetV be a vector space over ℚ. Let S(V) denote the symmetric algebra on V. Then, S(V)=⨁k=0∞Sk(V), where S0(V):=ℚ1, S1(V)=V, and Sk(V) is generated by the free commutative product of k elements of V. Also, let S(V)⊗n denote the n-fold tensor product of S(V) with itself. Recall that the multiplication in S(V)⊗n is given by the componentwise product:
(13)·:S(V)⊗n×S(V)⊗n→S(V)⊗n;(s1⊗⋯⊗sn,s1′⊗⋯⊗sn′)↦s1s1′⊗⋯⊗snsn′,
where si,  sj′ denote monomials on the elements of V for all i,j=1,…,n. We may now proceed to the correspondence between graphs on {1,…,n} and some elements of S(V)⊗n. First, for all i,j=1,…,n with i≠j, we define the following tensors in S(V)⊗n. 						(14)Ri,j:=1⊗i-1⊗v⊗1⊗j-i-1⊗v⊗1⊗n-j,
where v is any vector different from zero. (As in Section 3, for simplicity, our notation does not distinguish between elements, say, Ri,j∈S(V)⊗n and Ri,j∈S(V)⊗n′ with n≠n′. This convention will often be used in the rest of the paper for all the elements of the algebraic representation. Therefore, we will specify the set containing consider the given elements whenever necessary.) Now, for all i,j=1,…,n with i≠j, let (i)
a tensor factor in theith position correspond to the vertex i of a graph on {1,…,n},(ii)
a tensorRi,j∈S(V)⊗n correspond to the edge {i,j} of a graph on {1,…,n}.In this context, given a graphG with V(G)={1,…,n} and E(G)={{ik,jk}}k=1,…,m, we define the following algebraic representation of graphs.(a)
Ifm=0, then G is represented by the tensor 1⊗⋯⊗1∈S(V)⊗n.(b)
Ifm>0, then in S(V)⊗n the graph G yields a monomial on the tensors which represent the edges of G. More precisely, since for all 1≤k≤m each tensor Rik,jk∈S(V)⊗n represents an edge of the graph G, this is uniquely represented by the following tensor S1,…,nG∈S(V)⊗n given by the componentwise product of the tensors Rik,jk:
(15)S1,…,nG:=∏k=1m‍Rik,jk.Figure 4 shows some examples of this correspondence. Furthermore, let X⊆{1,…,n′} be a set of cardinality n with n′≥n. Also, let σ:{1,…,n}→X be a bijection. With this notation, define the following elements of S(V)⊗n′:
(16)Sσ(1),…,σ(n)G:=∏k=1m‍Rσ(ik),σ(jk).
In terms of graphs, the tensor Sσ(1),…,σ(n)G represents a disconnected graph, say, G′, on the set {1,…,n′} consisting of a graph isomorphic to G whose vertex set is X and n′-n isolated vertices in {1,…,n′}∖X. Figure 5 shows an example.(a) An isolated vertex represented by1∈S(V). (b) A 2-vertex tree represented by R1,2∈S(V)⊗2. (c) A triangle represented by R1,2·R1,3·R2,3∈S(V)⊗3.
(a)
(b)
(c)(a) The graph represented by the tensorS1,2,3,4G∈S(V)⊗4. (b) The graph represented by the tensor S1,5,4,2G∈S(V)⊗5 associated with G and the bijection σ:{1,2,3,4}→{1,2,4,5}; 1↦1,2↦5,3↦4,4↦2.
(a)
(b)Furthermore, letT(S(V)) denote the tensor algebra on the graded vector space S(V): T(S(V)):=⨁k=0∞S(V)⊗k. In T(S(V)) the multiplication
(17)•:T(S(V))×T(S(V))→T(S(V))
is given by concatenation of tensors (e.g., see [20–22]):
(18)(s1⊗⋯⊗sn)•(s1′⊗⋯⊗sn′′):=s1⊗⋯⊗sn⊗s1′⊗⋯⊗sn′′,
where si,sj′ denote monomials on the elements of V for all i=1,…,n and j=1,…,n′. We proceed to generalize the definition of the multiplication • to any two positions of the tensor factors. Let τ:S(V)⊗2→S(V)⊗2;s1⊗s2↦s2⊗s1. Moreover, define τk:=1⊗k-1⊗τ⊗1⊗n-k-1:S(V)⊗n→S(V)⊗n for all 1≤k≤n-1. In this context, for all 1≤i≤n, 1≤j≤n′, we define •i,j:S(V)⊗n×S(V)⊗n′→S(V)⊗n+n′ by the following equation:
(19)(s1⊗⋯⊗sn)•i,j(s1′⊗⋯⊗sn′′)∶=(τn-1∘⋯∘τi)(s1⊗⋯⊗sn)⊗(τ1∘⋯∘τj-1)(s1′⊗⋯⊗sn′′)=s1⊗⋯⊗s^i⊗⋯⊗sn⊗si⊗sj′⊗s1′⊗⋯⊗sj′^⊗⋯⊗sn′′,
where s^i (resp. sj′^) means that si (resp. sj′) is excluded from the sequence. In terms of the tensors S1,…,nG∈S(V)⊗n and S1,…,n′G′∈S(V)⊗n′ the equation previous yields
(20)S1,…,nG•i,jS1,…,n′G′:=Sσ(1),…,σ(n)G·Sσ′(1),…,σ′(n′)G′,
where Sσ(1),…,σ(n)G,Sσ′(1),…,σ′(n′)G′∈S(V)⊗n+n′, σ(k)=k if 1≤k<i, σ(i)=n, σ(k)=k-1 if i<k≤n, and σ′(k)=k+n+1 if 1≤k<j, σ′(j)=n+1, σ′(k)=k+n if j<k≤n′. Clearly, the tensor S1,…,nG•i,jS1,…,n′G′ represents a disconnected graph. Now, let ·i:=1⊗i-1⊗·⊗1⊗n-i-1:S(V)⊗n→S(V)⊗n-1. In T(S(V)), for all 1≤i≤n, 1≤j≤n′, define the following nonassociative and noncommutative multiplication:
(21)⋄i,j:=·n∘•i,j:S(V)⊗n×S(V)⊗n′→S(V)⊗n+n′-1.
The tensor S1,…,nG⋄i,jS1,…,n′G′ represents the graph on n+n′-1 vertices, say, H obtained by gluing the vertex i of the graph G to the vertex j of the graph G′. If both G and G′ are connected, the vertex n is clearly a cutvertex of the graph H. Figure 6 shows an example.(a) The graphs represented by the tensorsS1,2,3,4G∈S(V)⊗4 and S1,2,3G′∈S(V)⊗3. (b) The graph represented by the tensor S1,…,6H=S1,2,3,4G⋄3,2S1,2,3G′∈S(V)⊗6.
(a)
(b)


## 6. Linear Mappings

We recall some of the linear mappings given in [9].Letℬn,k⊂S(V)⊗n denote the vector space of all the tensors representing biconnected graphs in Vbiconnn,k. Let ℬ:=ℬ1,0⨁ℬ2,0⨁n=3∞⨁k=1kmax(n)ℬn,k⊂T(S(V)), where kmax(n)=(n(n-3)/2)+1 is, by Kirchhoff’s lemma [18], the maximum cyclomatic number of a biconnected graph on n vertices. Let the mapping Δ:ℬ→T(S(V)) be given by the following equations:
(22)Δ(1)∶=1⊗1,Δ(B1,…,nG)∶=1n∑i=1n‍Δi(B1,…,nG)ifn>1,
where G denotes a biconnected graph on n vertices represented by B1,…,nG∈S(V)⊗n. To define the mappings Δi, we introduce the following bijections:
(23)(i)σi:j↦{jif1≤j≤i,j+1ifi+1≤j≤n,(ii)νi:j↦{jif1≤j≤i-1,j+1ifi≤j≤n.
In this context, for all i=1,…,n with n>1, the mappings Δi:S(V)⊗n→S(V)⊗n+1 are defined by the following equation:
(24)Δi(B1,…,nG)∶=Bσi(1),…,σi(n)G+Bνi(1),…,νi(n)G=B1,…,i+1^,i+2,…,n+1G+B1,…,i^,i+1…,n+1G,
where i^ (resp., i+1^) means that the index i (resp., i+1) is excluded from the sequence. The tensor B1,…,i^,…,n+1G (resp., B1,…,i+1^,i+2,…,n+1G) is constructed from B1,…,nG by transferring the monomial on the elements of V which occupies the kth tensor factor to the (k+1)th position for all i≤k≤n (resp., i+1≤k≤n). Furthermore, suppose that Bπ(1),…,π(n)G∈S(V)⊗n′ and that the bijection π is such that i∉π({1,…,n})⊂{1,…,n′}. In this context, define
(25)Δi(Bπ(1),…,π(n)G)∶=Bνi(π(1)),…,νi(π(n))G
in agreement with Δ(1):=1⊗1. It is straightforward to verify that the mappings Δi satisfy the following property:
(26)Δi∘Δi=Δi+1∘Δi,
where we used the same notation for Δi:S(V)⊗n→S(V)⊗n+1 on the right of either side of the previous equation and Δi:S(V)⊗n+1→S(V)⊗n+2 as the leftmost operator on the left hand side of the equation. Accordingly, Δi+1:S(V)⊗n+1→S(V)⊗n+2 as the leftmost operator on the right hand side of the equation.Now, for allm>0, define the mth iterate of Δi, Δim:S(V)⊗n→S(V)⊗n+m, recursively as follows:
(27)Δi1∶=Δi,(28)Δim∶=Δi∘Δim-1,
where Δi:S(V)⊗n+m-1→S(V)⊗n+m in formula (28). This can be written in m different ways corresponding to the composition of Δim-1 with each of the mappings Δj:S(V)⊗n+m-1→S(V)⊗n+m with i≤j≤i+m-1. These are all equivalent by formula (26).Extension to Connected Graphs. We now extend the mappings Δi to the vector space of all the tensors representing connected graphs ℬ*:=⨁μ=0∞ℬ⋄μ, where ℬ⋄0=ℚ1. We proceed to define ℬ⋄μ for μ>0.First, given two setsAn⊂S(V)⊗n and Bp⊂S(V)⊗p, by An⋄i,jBp⊂S(V)⊗n+p-1 with i=1,…,n,j=1,…,p we denote the set of elements obtained by applying the mapping ⋄i,j to every ordered pair (a∈An,b∈Bp). Also, let ℬ2:=ℬ2,0 and ℬn:=⨁k=1kmax(n)ℬn,k, n≥3. In this context, for all μ≥1 and n≥μ+1, define ℬn*μ as follows:
(29)ℬn*μ=⋃n1+⋯+nμ=n+μ-1‍⋃i1=1n1‍⋯⋃iμ-1=1nμ-1‍⋃j1=1nμ+⋯+n2-μ+2‍⋯⋃jμ-1=1nμ‍ℬn1⋄i1,j1(ℬn2⋄i2,j2(⋯(ℬnμ-2⋄iμ-2,jμ-2(ℬnμ-1⋄iμ-1,jμ-1ℬnμ))⋯).
Also, define
(30)ℬn′*μ=⋃π∈Sn‍{Sπ(1),…,π(n)G∣S1,…,nG∈ℬn*μ},
where Sn denotes the symmetric group on the set {1,…,n} and Sπ(1),…,π(n)G is given by formula (16). Finally, for all μ≥1, define
(31)ℬ⋄μ:=⨁n=μ+1∞ℬn′*μ.
The elements of ℬ⋄μ are clearly tensors representing connected graphs on μ biconnected components. By (16) and (21), these may be seen as monomials on tensors representing biconnected graphs with the componentwise product · :S(V)⊗n×S(V)⊗n→S(V)⊗n so that repeated indices correspond to cutvertices of the associated graphs. In this context, an arbitrary connected graph, say, G, on n≥2 vertices and μ≥1 biconnected components yields
(32)∏a=1μ‍Bσa(1),…,σa(na)Ga,
Where, for all 1≤a≤μ, Bσa(1),…,σa(na)Ga∈S(V)⊗n, Ga is a biconnected graph on 2≤na≤n vertices represented by B1,…,naGa∈S(V)⊗na, and σa:{1,…,na}→Xa⊆{1,…,n} is a bijection.We now extend the mappingΔ:=(1/n)∑i=1n‍Δi to ℬ* by requiring the mappings Δi to satisfy the following condition:
(33)Δi(∏a=1μ‍Bσa(1),…,σa(na)Ga):=∏a=1μ‍Δi(Bσa(1),…,σa(na)Ga).
Given a connected graph G′, the mapping Δi may be thought of as a way of (a) splitting the vertex i into two new vertices numbered i and i+1 and (b) distributing the biconnected components sharing the vertex i between the two new ones in all the possible ways. Analogously, the action of the mappings Δim consists of (a) splitting the vertex i into m+1 new vertices numbered i,i+1,…,i+m and (b) distributing the biconnected components sharing the vertex i between the m+1 new ones in all the possible ways.We now combine the mappingsΔin-1 with tensors representing biconnected graphs. Let n>1, p≥1 and 1≤i≤p be fixed integers. Let πi:{1,…,n}→{i,i+1,…,i+n-1};j↦j+i-1 be a bijection. Let G be a biconnected graph on n vertices represented by the tensor B1,…,nG∈S(V)⊗n. The tensors Bi,i+1,…,i+n-1G:=Bπi(1),…,πi(n)G∈S(V)⊗n+p-1 (see formula (16)) may be viewed as operators acting on S(V)⊗n+p-1 by multiplication. In this context, consider the following mappings given by the composition of Bi,i+1,…,i+n-1G with Δin-1:
(34)Bi,i+1,…,i+n-1G∘Δin-1:S(V)⊗p→S(V)⊗n+p-1.
These are the analog of the mappings riG given in Section 3. In plain English, the mappings Bi,i+1,…,i+n-1G∘Δin-1 produce a connected graph with n+p-1 vertices from one with p vertices in the following way:(a)
split the vertexi into n new vertices, namely, i, i+1,…, i+n-1,(b)
distribute the biconnected components containing the split vertex between then new ones in all the possible ways,(c)
merge then new vertices into the graph G. When the graph G is a 2-vertex tree, the mapping R1,2∘Δ coincides with the application L=(ϕ⊗ϕ)Δ of [23] when ϕ acts on S(V) by multiplication with a vector.To illustrate the action of the mappingsBπi(1),…,πi(n)G∘Δi, consider the graph H consisting of two triangles sharing a vertex. Let this be represented by B1,2,3C3·B3,4,5C3∈S(V)⊗5, where C3 denotes a triangle represented by B1,2,3C3=R1,2·R2,3·R1,3∈S(V)⊗3. Let T2 denote a 2-vertex tree represented by B1,2T2=R1,2∈S(V)⊗2. Applying the mapping R3,4∘Δ3 to H yields
(35)R3,4∘Δ3(B1,2,3C3·B3,4,5C3)=R3,4·Δ3(B1,2,3C3)·Δ3(B3,4,5C3)=R3,4·(B1,2,3C3+B1,2,4C3)·(B3,5,6C3+B4,5,6C3)=R3,4·B1,2,3C3·B3,5,6C3+R3,4·B1,2,3C3·B4,5,6C3+R3,4·B1,2,4C3·B3,5,6C3+R3,4·B1,2,4C3·B4,5,6C3.
Figure 7 shows the linear combination of graphs given by (35) after taking into account that the first and fourth terms as well as the second and third correspond to isomorphic graphs. Note that 3 (resp. 4) is the only cutvertex of the graph represented by the first (resp. fourth) term, while 3 and 4 are both cutvertices of the graphs represented by the second or third terms.Figure 7
The linear combination of graphs obtained by applying the mappingR3,4∘Δ3 to the cutvertex of a graph consisting of two triangles sharing a vertex.


## 7. Further Recursion Relations

Reference [7] gives two recursion formulas to generate all the equivalence classes of trees with coefficients given by the inverses of the orders of their groups of automorphisms. On the one hand, the main formula is such that larger trees are produced from smaller ones by increasing the number of their biconnected components by one unit. On the other hand, the alternative formula is such that for all n≥2, trees on n vertices are produced by connecting a vertex of a tree on i vertices to a vertex of a tree on n-i vertices in all the possible ways. Theorem 1 generalizes the main formula to connected graphs. It is the aim of this section to derive an alternative formula for a simplified version of the latter.LetG denote a connected graph. Recall the notation introduced in Section 4; 𝒱G denotes the set of biconnected components of G and ℰ(𝒱G) denotes the set of equivalence classes of the graphs in 𝒱G. Given a set X⊂∪p=2n∪q=0kVbiconnp,q, let VXn,k:={G∈Vconnn,k:ℰ(𝒱G)⊆ℰ(X)} with the convention VX1,0:={({1},∅)}. With this notation, in the algebraic setting, Corollary 6 reads as follows.Theorem 7.
For allp>1 and q≥0, suppose that Φ1,…,pp,q:=∑G′∈Xp,q‍σG′B1,…,pG′∈ℬp,q⊂S(V)⊗p with σG′∈ℚ and Xp,q⊆Vbiconnp,q, is such that for any equivalence class 𝒜∈ℰ(Xp,q) the following holds: (i) there exists G′∈𝒜 such that σG′>0, (ii) ∑G′∈𝒜‍σG′=1/|aut𝒜|. In this context, for all n≥1 and k≥0, define Ψn,k∈S(V)⊗n by the following recursion relation:
(36)Ψ1,0∶=1,Ψ1,k∶=0ifk>0,(37)Ψn,k∶=1k+n-1×∑q=0k‍∑p=2n‍∑i=1n-p+1‍((q+p-1)Φi,i+1,…,i+p-1p,q·Δip-1(Ψn-p+1,k-q)).
Then, Ψn,k=∑G∈VXn,k‍αGS1,…,nG, where αG∈ℚ and X:=∪p=2n∪q=0kXp,q. Moreover, for any equivalence class 𝒞∈ℰ(VXn,k), the following holds: (i) there exists G∈𝒞 such that αG>0, (ii) ∑G∈𝒞‍αG=1/|aut𝒞|.Now, given a nonempty setY⊆Vbiconnp,q, we use the following notation:
(38)VYμ:={G∈Vconn(p-1)μ+1,qμ:ℰ(𝒱G)⊆ℰ(Y),card(𝒱G)=μ},
with the convention VY0:={({1},∅)}. When we only consider graphs whose biconnected components are all in Y, the previous recurrence can be transformed into one on the number of biconnected components.Theorem 8.
Letp>1 and q≥0 be fixed integers. Let Y⊆Vbiconnp,q be a non-empty set. Suppose that ϕ1,…,pp,q:=∑G′∈Y‍σG′B1,…,pG′∈ℬp,q⊂S(V)⊗p with σG′∈ℚ, is such that for any equivalence class 𝒜∈ℰ(Y) the following holds: (i) there exists G′∈𝒜 such that σG′>0, (ii) ∑G′∈𝒜‍σG′=1/|aut(𝒜)|. In this context, for all μ≥0, define ψμ∈S(V)⊗(p-1)μ+1 by the following recursion relation:
(39)ψ0:=1,ψμ:=1μ∑i=1(p-1)(μ-1)+1‍ϕi,i+1,…,i+p-1p,q·Δip-1(ψμ-1).
Then, ψμ=∑G∈VYμ‍αGS1,…,(p-1)μ+1G with αG∈ℚ. Moreover, for any equivalence class 𝒞∈ℰ(VYμ), the following holds: (i) there exists G∈𝒞 such that αG>0, (ii) ∑G∈𝒞‍αG=1/|aut(𝒞)|.Proof.
In this case,Ψn,k=0 unless n=(p-1)μ+1 and k=qμ, where μ≥0. Therefore, the recurrence of Theorem 7 can be easily converted into a recurrence on the number of biconnected components by setting ψμ:=Ψ(p-1)μ+1,qμ.Forp=2 and q=0, we recover the formula to generate trees of [7]. As in that paper and [8, 23], we may extend the result to obtain further interesting recursion relations.Proposition 9.
For allμ>0,
(40)ψμ=1μ×∑i1+⋯+ip=μ-1‍(∑a1=1(p-1)i1+1∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍⋯∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍ϕa1,…,app,q)·(ψi1⊗⋯⊗ψip),
where ij=0,…,μ-1 for all j=1,…,p.Proof.
Equation (40) is proved by induction on the number of biconnected components μ. This is easily verified for μ=1:
(41)ψ1=ϕ1,…pp,q·(1⊗⋯⊗1)=ϕ1,…pp,q.
We now assume the formula to hold for ψμ-1. Then, formula (37) yields
(42)ψμ=1μ∑i=1(p-1)(μ-1)+1‍ϕi,i+1,…,i+p-1p,q·Δip-1(ψμ-1)=1μ(μ-1)∑i=1(p-1)(μ-1)+1‍ϕi,i+1,…,i+p-1p,q·Δip-1(∑i1+⋯+ip=μ-2‍(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍⋯∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍ϕa1,…,app,q)·(ψi1⊗⋯⊗ψip)∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍)=1μ(μ-1)×∑i1+⋯+ip=μ-2‍∑i=1(p-1)(μ-1)+1‍(∑a1=1(p-1)i1+1‍Δip-1(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍⋯∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍ϕa1,…,app,q)·ϕi,i+1,…,i+p-1p,q·Δip-1(ψi1⊗⋯⊗ψip)∑a1=1(p-1)i1+1‍)=1μ(μ-1)×(∑i1+⋯+ip=μ-2‍(∑i=1(p-1)i1+1‍Δip-1(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍⋯∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍ϕa1,…,app,q)·ϕi,i+1,…,i+p-1p,q·(Δip-1(ψi1)⊗⋯⊗ψip)+∑i=(p-1)i1+2(p-1)(i1+i2)+2‍Δip-1(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍⋯∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍)·ϕi,i+1,…,i+p-1p,q·(ψi1⊗Δip-1(ψi2)⊗⋯⊗ψip)+⋯+∑i=(p-1)(i1+i2+⋯+ip-1)+p(p-1)(i+1+⋯+ip)+p‍Δip-1(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+2⋯∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍ϕa1,…,app,q)·ϕi,i+1,…,i+p-1p,q·(ψi1⊗⋯⊗Δip-1(ψip))∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍))=1μ(μ-1)×(∑i1+⋯+ip=μ-2‍(∑a1=1(p-1)i1+p‍(i1+1)×(∑a1=1(p-1)i1+p‍∑a2=(p-1)i1+p+1(p-1)(i1+i2)+p+1‍⋯∑ap=(p-1)(i1+⋯+ip-1)+2p-1(p-1)(i1+⋯+ip)+2p-1‍ϕa1,…,app,q)·(ψi1+1⊗⋯⊗ψip)+(i2+1)×(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+p+1‍⋯∑ap=(p-1)(i1+⋯+ip-1)+2p-1(p-1)(i1+⋯+ip)+2p-1‍ϕa1,…,app,q)·ϕi,i+1,…,i+p-1p,q·(ψi1⊗ψi2+1⊗⋯⊗ψip)+⋯+(ip+1)×(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍⋯∑ap=(p-1)(i1+⋯+ip-1)+2p-1(p-1)(i1+⋯+ip)+p‍ϕa1,…,app,q)·ϕi,i+1,…,i+p-1p,q·(ψi1⊗⋯⊗ψip+1)∑ap=(p-1)(i1+⋯⋯+ip-1)+2p-1(p-1)(i1+⋯+ip)+p‍))=1μ(μ-1)×(∑i1=0μ-1‍∑i2+⋯+ip=μ-1-i1‍i1+∑i2=0μ-1‍∑i1+i3+⋯+ip=μ-1-i2‍i2+⋯+∑ip=0μ-1‍∑i1+⋯+ip-1=μ-1-ip‍ip)×(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍⋯∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍ϕa1,…,app,q)·(ψi1⊗⋯⊗ψip)=1μ∑i2+⋯+ip=μ-1‍(∑a1=1(p-1)i1+1‍∑a2=(p-1)i1+2(p-1)(i1+i2)+2‍1μ∑i2+⋯+ip=μ-1‍⋯∑ap=(p-1)(i1+⋯+ip-1)+p(p-1)(i1+⋯+ip)+p‍ϕa1,…,app,q)·(ψi1⊗⋯⊗ψip).Note that formula (40) states that the linear combination of all the equivalence classes of connected graphs in VYμ is given by summing over all the p-tuples of connected graphs with total number of biconnected components equal to μ-1, gluing a vertex of each of them to distinct vertices of a graph in ℰ(Y) in all the possible ways.


## 8. Cayley-Type Formulas

LetY⊆Vbiconnp,q. Recall that VYμ is the set of connected graphs on μ biconnected components, each of which has p vertices and cyclomatic number q and is isomorphic to a graph in Y. We proceed to use formula (40) to recover some enumerative results which are usually obtained via generating functions and the Lagrange inversion formula, see [3]. In particular, we extend to graphs in VYμ the result that the sum of the inverses of the orders of the groups of automorphisms of all the pairwise nonisomorphic trees on n vertices equals nn-2/n! [12, page 209].Proposition 10.
Letp>1 and q≥0 be fixed integers. Let Y⊆Vbiconnp,q be a non-empty set. For all μ≥0,
(43)∑𝒞∈ℰ(VYμ)‍1|aut𝒞|=((p-1)μ+1)μ-2μ!(p∑𝒜∈ℰ(Y)‍1|aut𝒜|)μ.Proof.
We first recall the following well-known identities derived from Abel’s binomial theorem [14]:
(44)∑i=1n-1‍(ni)ii-1(n-i)n-i-1=2(n-1)nn-2,(45)∑i=0n‍(ni)(x+i)i-1(y+(n-i))n-i-1=(1x+1y)(x+y+n)n-1,
where x and y are non-zero numbers. A proof may be found in [15] for instance. From (45) follows that for all p>1 and non-zero numbers x1,…,xp, the identity
(46)∑i1+⋯+ip=n‍(ni1,…,ip)(x1+i1)i1-1⋯(xp+ip)ip-1=x1+⋯+xpx1⋯xp(x1+⋯+xp+n)n-1
holds. The proof proceeds by induction. For p=2 the identity specializes to (45). We assume the identity (46) to hold for p-1. Then,
(47)∑i1+⋯+ip=n‍(ni1,…,ip)(x1+i1)i1-1⋯(xp+ip)ip-1=∑i1=0n‍∑i2+⋯+ip=n-i1‍(ni1)(n-i1i2,…,ip)×(x1+i1)i1-1⋯(xp+ip)ip-1=x2+⋯+xpx2⋯xp×∑i1=0n‍(ni1)(x1+i1)i1-1(x2+⋯+xp+n-i1)n-i1-1=x2+⋯+xpx2⋯xp×(1x1+1x2+⋯+xp)(x1+⋯+xp+n)n-1=x1+⋯+xpx1⋯xp(x1+⋯+xp+n)n-1.
We turn to the proof of formula (43). Let I(μ):=∑𝒞∈ℰ(VYμ)‍(1/|aut𝒞|). Formula (40) induces the following recurrence for I(μ):
(48)I(0)=1,I(μ)=1μ∑𝒜∈ℰ(Y)‍1|aut𝒜|×∑i1+⋯+ip=μ-1‍((p-1)i1+1)⋯((p-1)ip+1)I(i1)⋯I(ip).
We proceed to prove by induction that I(μ)=(((p-1)μ+1)μ-2/μ!)(p∑𝒜∈ℰ(Y)‍(1/|aut𝒜|))μ. The result holds for μ=0,1:
(49)I(0)=1,I(1)=∑𝒜∈ℰ(Y)‍1|aut𝒜|.
We assume the result to hold for all 0≤i≤μ-1. Then,
(50)I(μ)=1μ∑i1+⋯+ip=μ-1‍((p-1)i1+1)⋯((p-1)ip+1)I(i1)⋯I(ip)∑𝒜∈ℰ(Y)‍1|aut𝒜|(51)=pμ-1μ∑i1+⋯+ip=μ-1‍1i1!⋯ip!((p-1)i1+1)i1-1⋯((p-1)ip+1)ip-1(∑𝒜∈ℰ(Y)‍1|aut𝒜|)μ(52)=pμ-1μ!(p-1)μ-1-p×∑i1+⋯+ip=μ-1‍(μ-1i1,…,ip)(i1+1p-1)i1-1⋯(ip+1p-1)ip-1(∑𝒜∈ℰ(Y)‍1|aut𝒜|)μ(53)=1μ!(p-1)μ-1-p(p-1)p-1×(μ-1+pp-1)μ-2(p∑𝒜∈ℰ(Y)‍1|aut𝒜|)μ(54)=1μ!((p-1)μ+1)μ-2(p∑𝒜∈ℰ(Y)‍1|aut𝒜|)μ,
where we used formula (46) in going from (52) to (53). This completes the proof of Proposition 10.The corollary is now established.Corollary 11.
Letp>1 and q≥0 be fixed integers. Let Y⊆Vbiconnp,q be a non-empty set. For all μ≥0, {G∈VYμ∣V(G)={1,…,(p-1)μ+1} is a set of cardinality
(55)((p-1)μ+1)!((p-1)μ+1)μ-2μ!(p∑𝒜∈ℰ(Y)‍1|aut𝒜|)μ.Proof.
The result is a straightforward application of Lagrange’s theorem to the symmetric group on the set{1,…,(p-1)μ+1} and each of its subgroups aut𝒞, forall𝒞∈ℰ(VYμ).Forp=2 and q=0, formula (55) specializes to Cayley’s formula [11]:
(56)(μ+1)μ-1=nn-2,
where n=μ+1 is the number of vertices of all the trees with μ biconnected components. In this particular case, the recurrence given by formula (48) can be easily transformed into a recurrence on the number of vertices n:
(57)J(1)=1,J(n)=12(n-1)∑i=1n-1‍i(n-i)J(i)J(n-i),
which by (44) yields J(n)=nn-2/n!. Now, for T(n)=n!J(n), we obtain Dziobek’s recurrence for Cayley’s formula [10, 24]:
(58)T(1)=1,T(n)=12(n-1)∑i=1n-1‍(ni)i(n-i)T(i)T(n-i).
Furthermore, for graphs whose biconnected components are all complete graphs on p vertices, formula (55) yields
(59)((p-1)μ+1)!((p-1)μ+1)μ-2(p-1)!μμ!
in agreement with Husimi’s result for this particular case [25] (see also [26]). Also, when the biconnected components are all cycles of length p, we recover a particular case of Leroux’s result [27]:
(60)((p-1)μ+1)!((p-1)μ+1)μ-22μμ!.



---

*Source: 347613-2013-03-04.xml*