
\subsection*{Acknowledgments}

We would like to thank Christian Brouder who, after learning about our
main result, suggested the recursion formula of
Proposition~\ref{prop:alternativenew}, which we subsequently
proved. One of the authors (\^A.~M.) was supported through a
fellowship provided by Funda\c c\~ao Calouste Gulbenkian 65709.

\section{Further recursion relations}
\label{sec:recrel}

Generalizing the case with trees (Section~V in \cite{MeOe:npoint}) we
present an alternative recursion relation satisfied by
$\Omega^{l,v}$. This has the advantage over (\ref{eq:recomega})
that it may be translated directly into a recursion relation of the
resulting $n$-point functions $\sigma^{l,v}$, related via
Corollary~\ref{cor:loopexpansion}.

\begin{prop}
\label{prop:alternativenew}
Let $v\ge 1$ and $l\ge 0$, but not $v=1$ and $l=0$. Then,
\begin{equation*}
\Omega^{l,v}
=\frac{1}{l+v-1}\left(
\Omega^{l-1,v}\circT
+ \sum_{a=0}^{l}\sum_{b=1}^{v-1}
\left(\Omega^{a,b}\otimes\Omega^{l-a,v-b}\right)\circQ \right) .
\end{equation*}
It is understood that the first summand does not contribute if $l=0$
while the second does not contribute if $v=1$.
\end{prop}

Before proceeding with the proof we note that this formula has a
straightforward interpretation in terms of sums over weighted
graphs following the correspondence of Section~\ref{sec:grep}.
Namely, the formula states that the weighted sum over graphs
with $l$ loops and  $v$ vertices is given by a sum of two
terms divided by the edge number $e=l+v-1$.
The first term is the sum over all weighted graphs with
$l-1$ loops and  $v$ vertices which have an extra edge
attached, its endpoints being connected to vertices in all possible
ways.
The second term is a sum over
all ordered pairs of weighted graphs with total number of
vertices equal to $v$ and total number of loops equal to
$l$, connected in all possible ways with an edge.


\begin{proof}
The proof proceeds by induction on the number of edges $e=l+v-1$
(recall Lemma \ref{lem:loopnumber}). It is straightforward to check
its validity for $e=1$ by reducing the cases $l=0$, $v=2$ and
$l=1$, $v=1$ to (\ref{eq:recomega}), remembering that $\Omega^{0,1}$
is the identity.

We now assume the formula to hold for any edge number
smaller than a fixed $e\ge 2$.  Then for loop number $l$ and vertex number
$v$ such that $e=l+v-1$ we use (\ref{eq:recomega}) to show the
following equality and hence complete the proof.
\begin{flalign*}
& \Omega^{l,v} = \frac{1}{l+v-1}\left(\sum_{j=1}^{v-1}Q_j
\circ\Omega^{l,v-1}
+\sum_{j=1}^{v}T_j\circ\Omega^{l-1,v}\right)\\
& = \frac{1}{(l+v-1)(l+v-2)}\cdot\\
& \quad \biggl(\sum_{j=1}^{v-1}Q_j \circ
\biggl(
 \Omega^{l-1,v-1}\circT
+ \sum_{a=0}^{l}\sum_{b=1}^{v-2}
 \left(\Omega^{a,b}\otimes\Omega^{l-a,v-1-b}\right)
\circQ \biggr) \\
& \quad +
\sum_{j=1}^{v}T_j\circ\biggl(
 \Omega^{l-2,v}\circT
+ \sum_{a=0}^{l-1}\sum_{b=1}^{v-1}
 \left(\Omega^{a,b}\otimes\Omega^{l-1-a,v-b}\right) \circQ
\biggr)\biggr)\\
& = \frac{1}{(l+v-1)(l+v-2)}\cdot\biggl(
 \sum_{j=1}^{v-1}Q_j\circ \Omega^{l-1,v-1}\circT
+ \sum_{j=1}^{v}T_j\circ\Omega^{l-2,v}\circT\\
& \quad +
 \sum_{a=0}^{l}\sum_{b=1}^{v-2}\biggl(
 \sum_{j=1}^{b}Q_j\circ\Omega^{a,b}
 \otimes\Omega^{l-a,v-1-b}\\
& \quad +
 \sum_{j=1}^{v-1-b}
 \Omega^{a,b}\otimes
 Q_j\circ\Omega^{l-a,v-1-b}\biggr)
 \circQ\\
& \quad +
\sum_{a=0}^{l-1}\sum_{b=1}^{v-1}\biggl(\sum_{j=1}^{b}T_j\circ
\Omega^{a,b}\otimes\Omega^{l-1-a,v-b}\\
& \quad + \sum_{j=1}^{v-b}
\Omega^{a,b}\otimesT_j\circ\Omega^{l-1-a,v-b}\biggr)\circQ
\biggr)\\
& = \frac{1}{(l+v-1)(l+v-2)}\cdot\biggl(
\biggl(\sum_{j=1}^{v-1}Q_j\circ
\Omega^{l-1,v-1}+\sum_{j=1}^{v}T_j\circ\Omega^{l-2,v}\biggr)\circT
\\
& \quad +
 \biggl(\sum_{b=1}^{v-2}\biggl(\sum_{j=1}^{b}
 \left(Q_j\circ\Omega^{0,b}\right) \otimes\Omega^{l,v-1-b}
+\sum_{j=1}^{v-1-b}\Omega^{l,b}\otimes
 \left(Q_j\circ\Omega^{0,v-1-b}\right)\biggr) \\
& \quad + \sum_{a=0}^{l-1}\biggl(\left(T\circ
\Omega^{a,1}\right)\otimes\Omega^{l-1-a,v-1}
+ \Omega^{a,v-1}\otimes\left(T\circ\Omega^{l-1-a,1}\right)\biggr) \\
&\quad +
\sum_{a=1}^{l}\sum_{b=2}^{v-1}\biggl(
 \sum_{j=1}^{b-1}Q_j\circ\Omega^{a,b-1}
+ \sum_{j=1}^{b}T_j\circ\Omega^{a-1,b}\biggr)
 \otimes\Omega^{l-a,v-b} \\
& \quad +
 \sum_{a=0}^{l-1}\sum_{b=1}^{v-2}
 \Omega^{a,b}\otimes\biggl(\sum_{j=1}^{v-1-b}Q_j
 \circ\Omega^{l-a,v-1-b}
 + \sum_{j=1}^{v-b}T_j\circ\Omega^{l-1-a,v-b}\biggr)\biggr)
 \circQ\biggr)\\
& = \frac{1}{(l+v-1)(l+v-2)}\cdot\biggl(
(l+v-2)\,\Omega^{l-1,v}\circT\\
& \quad +
 \biggl(\sum_{b=2}^{v-1}(b-1)\,\Omega^{0,b}
 \otimes\Omega^{l,v-b}
 +\sum_{b=1}^{v-2}(v-b-1)\,\Omega^{l,b}\otimes\Omega^{0,v-b}\\
& \quad + \sum_{a=1}^{l} a\,
 \Omega^{a,1}\otimes\Omega^{l-a,v-1}
 + \sum_{a=0}^{l-1} (l-a)\,
 \Omega^{a,v-1}\otimes\Omega^{l-a,1} \\
&\quad +
 \sum_{a=1}^{l}\sum_{b=2}^{v-1} (a+b-1)\,\Omega^{a,b}
 \otimes\Omega^{l-a,v-b}\\
& \quad +
\sum_{a=0}^{l-1}\sum_{b=1}^{v-2} (l-a+v-b-1)\,\Omega^{a,b}\otimes
\Omega^{l-a,v-b}\biggr)\circQ\biggr)\\
& = \frac{1}{(l+v-1)(l+v-2)}\cdot\biggl(
 (l+v-2)\,\Omega^{l-1,v}\circT \\
& \quad +
\biggl(\sum_{a=0}^{l}\sum_{b=1}^{v-1}
(a+b-1)\,\Omega^{a,b}\otimes\Omega^{l-a,v-b} \\
& \quad +
\sum_{a=0}^{l}\sum_{b=1}^{v-1} (l-a+v-b-1)\,\Omega^{a,b}\otimes
\Omega^{l-a,v-b}\biggr)\circQ\biggr)\\
& =\frac{1}{l+v-1}\left(\Omega^{l-1,v}\circT
 + \sum_{a=0}^{l}\sum_{b=1}^{v-1}
 \left(\Omega^{a,b}\otimes\Omega^{l-a,v-b}\right)
\circQ\right) .
\end{flalign*}
\end{proof}

Combining this result with Corollary~\ref{cor:loopexpansion} yields
the corresponding recursion equation for $\sigma^{l,v}$.
\begin{cor}
\label{cor:recnew}
Let $v\ge 1$ and $l\ge 0$, but not $v=1$ and $l=0$. Then,
\begin{equation*}
\sigma^{l,v}
=\frac{1}{l+v-1}\left(
\sigma^{l-1,v}\circT
+ \sum_{a=0}^{l}\sum_{b=1}^{v-1}
\left(\sigma^{a,b}\otimes\sigma^{l-a,v-b}\right)\circQ \right) .
\end{equation*}
It is understood that the first summand does not contribute if $l=0$
while the second does not contribute if $v=1$.
\end{cor}

\section{Appendix}

This appendix shows all graphs without external edges and
with up to three edges computed as contributions to
$\Omega^{l,v}(\mathbf{1})$
via (\ref{eq:recomega}).  The factors in front of the graphs are the
inverses of their
symmetry factors of Definition~\ref{def:symfac}, see
Theorem~\ref{thm:main}.
\vspace{1cm}\\
\input{figures/l0v1.eepic}
\vspace{1cm}\\
\input{figures/l0v2.eepic}
\vspace{1cm}\\
\input{figures/l1v1.eepic}
\vspace{1cm}\\
\input{figures/l0v3.eepic}
\vspace{1cm}\\
\input{figures/l1v2.eepic}
\vspace{1cm}\\
\input{figures/l2v1.eepic}
\vspace{1cm}\\
\input{figures/l0v4.eepic}
\vspace{1cm}\\
\input{figures/l1v3.eepic}
\vspace{1cm}\\
\input{figures/l2v2.eepic}
\vspace{1cm}\\
\input{figures/l3v1.eepic}
\\

\section{Basic concepts and definitions}
\label{sec:basics}

The basic setup in this paper is substantially similar to that of
\cite{MeOe:npoint}. Hence, the present section has substantial overlap
with Section~II and a part of Section~IV of that paper. Nevertheless,
there are important differences, most importantly a more extensive treatment
of abstract graphs and their symmetries.

\subsection{Graphs}
\label{sec:graphs}

We introduce certain kinds of graphs and elementary properties of
them. The graphs will be later interpreted as Feynman graphs. Here we
are only interested in them as abstract graphs.


\begin{dfn}
A \emph{graph} is a finite collection of \emph{vertices} and
\emph{edges}, such that any
end of an edge may be connected to a vertex.
Edges that are connected to vertices at both ends are
called \emph{internal}, while edges with at least one free end are
called \emph{external}. Internal edges with both ends connected to the
same vertex are also called \emph{self-loops}.
The \emph{valence} of a vertex is the number of ends of edges
connected to the vertex. The \emph{loop number} of a graph is its
number of cycles. A graph is \emph{connected} if it is connected as a
topological space.
\end{dfn}

We recall the well known relation between vertex number, edge number
and loop number of connected graphs:

\begin{lem}
\label{lem:loopnumber}
Consider a connected graph with at least one vertex.
Let $v,e,l$ be its number of vertices,
internal edges and loops, respectively. Then,
\begin{equation}
\label{eq:loopnumber}
l=e-v+1\,.
\end{equation}
\end{lem}  

\begin{dfn}
A \emph{labeled} graph is a graph whose free ends of external edges
are labeled with labels from a label set. Labels on different ends of
edges are required to be distinct.
\end{dfn}

In the following we shall consider only such labeled graphs, i.e.,
from now on \emph{graph} means \emph{labeled graph}. The label set is
fixed from the outset and will later be identified with an appropriate
set of field operator labels.

\begin{dfn}
\label{def:order}
A graph is said to be \emph{vertex ordered} if its vertices are
ordered. That is, the vertices are numbered $1,\dots,n$ where $n$ is
the total number of vertices.
A graph is said to be \emph{edge ordered} if the ends of its internal
edges are ordered. That is, the ends of internal edges are numbered
$1,\dots,2 n$ where $n$ is the total number of internal edges (each
edge having two ends).
A graph is called \emph{ordered} if it is both
vertex ordered and edge ordered.
\end{dfn}

\begin{dfn}
\label{def:symfac}
Consider an ordered graph $\gamma$. A \emph{symmetry} of $\gamma$ is a
permutation of the numbering of the vertices and of the endpoints of
the internal edges that yields combinatorially the same ordered (and labeled)
graph. The number of symmetries, i.e., the order of the group of
permutations leaving the graph invariant, is called the \emph{symmetry
factor} of the graph. It will be denoted by $S^\gamma$.
\end{dfn}
 
Since the symmetry factor is the same for any ordering of the vertices
and ends of internal edges of a graph, the concept is well defined for
unordered graphs as well.

\begin{dfn}
\label{def:vertexsymfac}
Consider a vertex ordered graph $\gamma$. A \emph{vertex symmetry} of
$\gamma$ is a permutation of the numbering of its vertices, which
yields combinatorially the same vertex ordered (and labeled) graph. The
order of the group of vertex symmetries is called the \emph{vertex
  symmetry factor} of the graph. It will be denoted by
$S^\gamma_{\text{vertex}}$.
\end{dfn}

\begin{dfn}
\label{def:edgesymfac}
Consider an ordered graph $\gamma$.  An \emph{edge symmetry} of
$\gamma$ is a permutation of the numbering of the ends of its
internal edges that yields combinatorially the same ordered (and
labeled) graph while the order of the vertices is held fixed. The
order of the group of edge symmetries is called the \emph{edge
  symmetry factor} of the graph. It will be denoted by
$S^\gamma_{\text{edge}}$.
\end{dfn}

Clearly, the concepts of  vertex and edge symmetry factors also make
sense for unordered graphs as the vertex and edge symmetry factors are
the same for any ordering of the vertices and of the ends of the
internal edges of a graph, respectively.

\begin{lem}
\label{lem:sym}
Let $\gamma$ denote an ordered graph.
The orders of the associated symmetry groups satisfy
$S^{\gamma}=
S^{\gamma}_{\text{vertex}}\cdot
S^{\gamma}_{\text{edge}}$.
\end{lem}
\begin{proof}
Denote the group of symmetries, vertex symmetries and edge symmetries
of $\gamma$ by $G^\gamma$, $G^\gamma_\text{vertex}$ and
$G^\gamma_\text{edge}$ respectively. Note that an edge symmetry is
merely a particular type of symmetry. Hence,
the group $G^\gamma_\text{edge}$ may be seen as a subgroup of
$G^\gamma$ via an injective group
homomorphism $G^\gamma_\text{edge}\to G^\gamma$. Furthermore, a
symmetry defines a vertex symmetry by forgetting its action on the
numbering of ends of edges. On the other hand, any vertex symmetry
can be augmented to a symmetry. Hence, there is a surjective group
homomorphism $G^\gamma\to G^\gamma_\text{vertex}$.
It is easy to see that the group homomorphisms form an exact sequence of
groups
\[
 0\to G^\gamma_\text{edge}\to G^\gamma\to G^\gamma_\text{vertex}\to 0 .
\]
Hence, as the groups are finite their orders
satisfy $S^{\gamma}=
S^{\gamma}_{\text{vertex}}\cdot
S^{\gamma}_{\text{edge}}$.
\end{proof}

\begin{lem}
\label{lem:edgesymfac}
Consider a connected graph $\gamma$.
Let $v$ be its number of
vertices. For each vertex $1\le i\le v$ let $p_i$ be the number of
self-loops connected to it.
Let $t$ be the number of pairs of
vertices which are directly connected through at least one edge.
For each pair $1\le j\le t$ of such vertices let $q_j$ be the number of
edges connecting it. Then, the edge
symmetry factor of $\gamma$ is given by
$S^\gamma_{\text{edge}}=(\prod_{i=1}^v\, 2^{p_i}\cdot
p_i!)(\prod_{j=1}^t\,q_j!)$.
\end{lem}

The proof is straightforward combinatorics.


\subsection{$n$-point functions and Feynman graphs}
\label{sec:feyn}

The physical content of a quantum field theory is usually
extracted from its $n$-point functions. In perturbation theory, these
are computed as sums of values of Feynman graphs. We briefly
review here the essentials. More details can be found in any standard
text book on quantum field theory such as \cite{ItZu:qft}.

We denote by
$G^{(n)}(x_1,\dots,x_n)$ the \emph{complete} 
$n$-point function. This is the vacuum expectation value of
the time-ordered product of $n$ field operators, i.e.,
\[
 G^{(n)}(x_1,\dots,x_n)
 =\langle 0 | T \phi(x_1)\cdots \phi(x_n) | 0\rangle .
\]
The notation we use here suggests a scalar field theory on Minkowski
spacetime. In general there would be internal field indices as well
and possibly other modifications (other spacetime etc.).
The real nature of the fields is completely irrelevant
for our treatment as long as the standard perturbative treatment applies.
Therefore, we shall continue
with our present notation for simplicity. Hence, we denote field operators
generically by $\phi(x)$, where $x$ is from a label set (here
suggestive of points in Minkowski space).
Furthermore, we shall assume all fields to
be bosonic. The fermionic case is also straightforward, but includes
extra factors, see Section~\ref{sec:discuss}.

Let $V$ be the complex vector space of linear combinations of field
operators $\phi(x)$. The algebra generated by the field operators with
the \emph{time-ordered} product is commutative and can be identified
with the \emph{symmetric algebra} $\mathsf{S}(V)$ over $V$. More precisely,
$\mathsf{S}(V)=\bigoplus_{k=0}^\infty V^k$, where $V^k$ is the space of 
linear combinations of monomials of degree $k$ in the field operators
and $V^0$ is the one-dimensional vector space spanned by the identity
element $\mathbf{1}$.
We may now express ensembles of $n$-point functions as functions
$\mathsf{S}(V)\to\mathbb{C}$. In particular, we may set
\[
\rho(\phi(x_1)\cdots\phi(x_n)) := G^{(n)}(x_1,\dots,x_n) .
\]

In perturbation theory, the $n$-point functions can be computed
as a sum over values of Feynman graphs. For the complete $n$-point
functions we may write
\begin{equation}
 G^{(n)}(x_1,\dots,x_n)
 =\sum_{\gamma\in\Gamma^n} w_\gamma \gamma(x_1,\dots,x_n) .
\label{eq:npoint}
\end{equation}
Here $\Gamma_n$ is the set of Feynman graphs. These are graphs
$\gamma$ in the sense of Section~\ref{sec:graphs} with $n$
external edges labeled by field operator labels
$x_1,\dots,x_n$.\footnote{Note that usually Feynman graphs involve
lines of different type depending on particle species. In our treatment
lines correspond to sums over all particle species. The information
about which particle species can interact resides completely in the
vertex functions.}
Indeed, from here onward we
fix the label set to be the label set of the field operators.
The value of a
graph $\gamma$
labeled by $x_1,\dots,x_n$ is denoted above by
$\gamma(x_1,\dots,x_n)$. The set $\Gamma_n$ may be taken to be
precisely the set of all graphs with $n$ external legs (up to
topological equivalence). The
weight factor $w_\gamma$ is precisely the inverse of the symmetry
factor $S^\gamma$ of a graph in the sense of
Definition~\ref{def:symfac}.

We should emphasize that the discussion here applies to bare
$n$-point functions. Renormalization is outside the scope of the
present paper.

The type of $n$-point functions we shall be interested in in the
following are the \emph{connected} ones, denoted $G_c^{(n)}$. These
may be defined in the same way as (\ref{eq:npoint}), but with the
restriction that only connected graphs are considered. We define
$\sigma:\mathsf{S}(V)\to \mathbb{C}$ via
\[
 \sigma(\phi(x_1)\cdots\phi(x_n)) := G_c^{(n)}(x_1,\dots,x_n).
\]

We now turn to the calculation of the value of a Feynman graph.
The Feynman
propagator $G_F(x,y)$ is the value of the graph that consists of an
edge only, its two ends labeled by $x$ and $y$
respectively.
The value of a graph that consists of a vertex with external edges
labeled by $x_1,\dots,x_k$ is given by the vertex
function $F(x_1,\dots,x_k)$. Note that we can encode the ensemble of
vertex functions in a way analogous to $n$-point functions as a
function $\nu:\mathsf{S}(V)\to\mathbb{C}$ via
\begin{equation}
 \nu(\phi(x_1)\cdots\phi(x_n)):= F(x_1,\dots,x_n) .
\label{eq:vfunc}
\end{equation}

For more general graphs we also need the inverse Feynman propagator,
$G_F^{-1}$, determined by the 
equation
\begin{equation}
\int \mathrm{d} y\, G_F(x,y)G_F^{-1}(y,z)=\delta(x,z) .
\label{eq:invfey}
\end{equation}
The value of a general graph may then be computed as follows:
Associate a label with each internal edge and form the product over
a vertex function associated with each vertex and an inverse Feynman
propagator associated to each internal edge. Finally, integrate over
all possible assignments of internal labels.


\subsection{Algebraic representation of graphs}
\label{sec:grep}

We introduce an algebraic representation of graphs based on the
time-ordered operator algebra $\mathsf{S}(V)$ and allowing straightforward
evaluation of graphs in the above sense. More precisely, we associate
a given graph with $v$ vertices with a certain element in
$\mathsf{S}(V)^{\otimesv}$, the $v$-fold tensor product of $\mathsf{S}(V)$.

Each
vertex of the graph corresponds to one tensor factor. A product
$\phi(x_1)\cdots\phi(x_n)$ in a
given tensor factor corresponds to external edges of the associated
vertex whose endpoints are labeled by $x_1,\dots,x_n$.
To represent internal edges, we define the formal elements
$R_{i,j}\in\mathsf{S}(V)^{\otimes v}$ with
$1\le i\le j\le v$ using the inverse Feynman propagator
(\ref{eq:invfey}).\footnote{$R_{i,j}$ is
formal insofar as it  really lives in
a completion of the tensor product $\mathsf{S}(V)^{\otimesv}$. However,
this fact is largely irrelevant for our purposes.}
For $i\neq j$ the definition is
\begin{equation}\label{eq:Rij}
R_{i,j} := \int
\mathrm{d} x\,\mathrm{d} y\,G_F^{-1}(x,y)\,(\mathbf{1}^{\otimes i-1}\otimes \phi(x)
\otimes\mathbf{1}^{\otimes j-i-1}
\otimes\phi(y)\otimes\mathbf{1}^{\otimes v-j}) ,
\end{equation}
with the field operators $\phi(x)$ and $\phi(y)$
inserted at the $i^{\mbox{\tiny{th}}}$ and
$j^{\mbox{\tiny{th}}}$ positions, respectively.
For $i=j$ the definition is
\begin{equation}\label{eq:Rii}
R_{i,i} := \int
\mathrm{d} x\,\mathrm{d} y\,G_F^{-1}(x,y)\,(\mathbf{1}^{\otimes i-1}\otimes \phi(x)
\phi(y)\otimes\mathbf{1}^{\otimes v-i}) ,
\end{equation}
The element $R_{i,j}\in\mathsf{S}(V)^{\otimesv}$ corresponds to one
internal edge connecting
the vertices which occupy the positions $i$ and $j$. In particular,
the element $R_{ i,i}\in\mathsf{S}(V)^{\otimesv}$ for $1\le i\lev$
is interpreted as an internal edge connecting the
$i^{\mbox{\tiny{th}}}$ vertex to itself. That is, it corresponds to a
self-loop.

Combining several internal edges (which can be self-loops) and their
products with external edges by multiplying the respective
expressions in $\mathsf{S}(V)^{\otimes v}$ allows to build arbitrary graphs
with $v$ vertices. Figure~\ref{fig:exacor} shows some
examples. It is then obvious that applying the vertex functions $\nu$
defined by (\ref{eq:vfunc}) to each tensor factor yields precisely the
value of the respective graph as a Feynman graph. Thus, the graphs
we just discussed are exactly those
that are to enter in the $v$-vertex  contribution to an
$n$-point function.

\begin{figure}
\input{figures/3graphs.eepic}
\caption{Examples of the algebraic representation of graphs in terms
of elements of $\mathsf{S}(V)^{\otimes v}$.}
\label{fig:exacor}
\end{figure}

The ordering of the tensor factors of $\mathsf{S}(V)^{\otimes v}$
induces an ordering of the vertices of the graphs in the sense of
Definition \ref{def:order}. However, when applying
$\nu^{\otimes v}$ the ordering is ``forgotten''. Indeed, it is not
relevant for the interpretation of graphs as Feynman graphs, but
only plays a role at
the level of their algebraic representation here. 
In the following, we will encounter elements of $\mathsf{S}(V)^{\otimes v}$
that are linear combinations of expressions corresponding to
graphs. In this context, we call the scalar multiplying the expression
for a given graph the \emph{weight} of the graph.
Clearly, if we are interested in unordered graphs, the weight of such
a graph is the sum of the weights of all vertex ordered graphs that
correspond to it upon forgetting the vertex order.


\subsection{The field operator algebra as a Hopf algebra}

A crucial ingredient of our setting is the fact that the algebra $\mathsf{S}(V)$
of time-ordered field operators is not only an algebra, but
a \emph{Hopf algebra}. That is, $\mathsf{S}(V)$ carries a coproduct $\cop:\mathsf{S}(V)\to
\mathsf{S}(V)\otimes \mathsf{S}(V)$ and a counit $\cou:\mathsf{S}(V)\to\mathbb{C}$ that are compatible with
its algebra structure and unit. ($\mathsf{S}(V)$ also carries an antipode map,
but this will not be used in the following.)
We refer the reader to \cite{Swe:hopfalg}
for a classical treatment of Hopf algebras and to \cite{Lan:algebra}
for the Hopf algebra structure of the symmetric algebra. The
significance of this Hopf
algebra structure for quantum field theory was developed in
\cite{BFFO:twist}. (Note,
however, that the product taken there is the normal product and not
the time-ordered one.)

At this point we will only mention the
explicit form of the coproduct on $\mathsf{S}(V)$. On monomials this takes the
form
\begin{equation}
\cop (\phi(x_1)\cdots \phi(x_n))=
 \sum_{I_1\cup I_2 = \{\phi(x_1),\dots,\phi(x_n)\}} T(I_1)\otimes T(I_2),
\label{eq:coproduct}
\end{equation}
and is extended to all of $\mathsf{S}(V)$ by linearity.
Here the sum runs over partitions of the set of field operators
$\{\phi(x_1),\dots,\phi(x_n)\}$ into two sets $I_1$ and $I_2$. $T$
denotes the time-ordered product of the field operators in the
corresponding partition. The coproduct may be extended (by suitable
composition with itself) to a map (on monomials and extended by
linearity),
\begin{equation}
\cop^k (\phi(x_1)\cdots \phi(x_n))=
 \sum_{I_1\cup \cdots\cup I_{k+1} = \{\phi(x_1),\dots,\phi(x_n)\}}
 T(I_1)\otimes \cdots \otimes T(I_{k+1}) .
\label{eq:copk}
\end{equation}
The difference to the single coproduct is that the set of field
operators is now split into $k+1$ partitions. Note also that the
partitions are \emph{ordered}, i.e., the sets $I_1,\dots, I_{k+1}$ are
distinguishable. An important property of the coproduct is that it is
multiplicative, i.e., it is an algebra map with respect to the algebra
structure of $\mathsf{S}(V)$ (and the induced algebra structure on the tensor
product).
A more
extensive discussion of the Hopf algebra structure, adapted to the
present context can be found in \cite{MeOe:npoint}.

\section{Discussion and Conclusion}
\label{sec:discuss}

The results of the present paper can be seen as an extension of those
of \cite{MeOe:npoint}, where only tree graphs were
generated. Accordingly, many points in the discussion of the main
result in that paper
extend to the present setting. In particular, this
applies to the algorithmic aspects and to the inclusion of
fermions. We refer the reader to Sections~VI.C and VI.D of
\cite{MeOe:npoint} for details. Here we shall only touch these points
briefly and highlight differences arising through the inclusion of
graphs with loops.

The generation of the graphs in their algebraic
representation via the recursion formula (\ref{eq:recomega})
has the structure of an algorithm. Indeed, this algorithmic structure
can be used directly and efficiently in implementing concrete
calculations of (loop) graphs. In doing so, external edges may be fixed
from the beginning and $\Omega^{l,v}$ as applied to the
external edges is calculated recursively rather than as an abstract map.
An important aspect for the
efficiency of concrete calculations is to discard graphs that do not
contribute. In typical quantum field theoretic calculations, the
vertex function is such that only vertices with a minimum valence
(usually three)
contribute. In the case of tree graphs this allows the restriction of
the coproduct implicit in the operator $Q_i$ in the recursion formula
(\ref{eq:recomega}) \cite{MeOe:npoint}. Concretely,
the coproduct (\ref{eq:coproduct})
may be replaced by a \emph{truncated} coproduct $\cop_{\ge k}$ with
$k\ge 1$. This
is defined by removing from the right hand side of
(\ref{eq:coproduct}) all terms where the number of elements in $I_1$
or $I_2$ is smaller than $k$. This will prevent graphs from being
generated who have vertices with valence smaller than $k+1$. If only
tree graphs are considered this is consistent with the recursion
process. More precisely, a graph with all vertices of valence at least
$k+1$ cannot be generated by $Q_i$ from a graph with at least one vertex
having valence smaller than $k+1$. The analogous statement is
not true for the operator $T_i$. Hence, considering loop graphs as
well (recall that $T_i$ increases loop number), we can no longer
globally restrict the coproduct. However, if we are interested in
graphs only up to a maximal loop number $m$, we may still restrict the
coproduct in $Q_i$ in certain instances. These are precisely the
instances when a later application of $T_i$ to a graph cannot occur,
i.e., when the graph has already the maximal loop number $m$.

The restriction on the valence of vertices to be at least $a$, where
$a\ge 3$, leads to another obvious limit we can impose on the
algorithm. Namely, for a given number of loops $m$ and a given number
of external edges $n$ there is an upper bound $b= (n+2m-2)/(a-2)$
on the number of
vertices a graph can have. Thus, in this case we only need to compute
$\Omega^{l,v}$ for $l\le m$ and
$v\le b$.

We now turn to the question of the implementation of fermions. Here
the situation is not at all changed by the extension to loop
graphs. Namely, the whole formalism is completely functorial and
carries over immediately to the case that the vector space $V$ of
field operators is a $\mathbb{Z}_2$-graded space. (Recall that this means that
$V$ is a direct sum of a bosonic and fermionic part.) Concretely,
certain field operators will anticommute which introduces minus signs
in front the summands in (\ref{eq:coproduct}) and (\ref{eq:copk})
which correspond to odd permutations of such field operators. In
contrast, all formulas appearing in Section~\ref{sec:loop} and
\ref{sec:recrel} remain
unchanged as the $\mathbb{Z}_2$-grading is completely implicit there.

The algorithm to generate tree graphs was applied in two contexts in
\cite{MeOe:npoint}: To relate connected $n$-point functions with
1-particle irreducible ones and to generate all tree graphs using the
vertex functions. In both cases renormalization does not introduce any
alteration. This is different in the present situation where we
interpret the algorithms of Section~\ref{sec:loop} and
\ref{sec:recrel} as generating all
connected graphs using the vertex functions. Renormalization, via
counter-terms, alters this process considerably. Thus, it would be
highly desirable to include the renormalization process into the present
framework. At this point we have very little to say about this, except
to point out that the algorithms of Section~\ref{sec:loop} and
\ref{sec:recrel} are
naturally organized as a recursion by loop order, which might
facilitate the task.


\section{Generating loop graphs}
\label{sec:loop}


\subsection{Statement of result}

The main result of this paper, which is the subject of the present
section, may be described as an efficient
algorithm that recursively generates all connected graphs $\gamma$.
The graphs are generated together with the correct weights $w_\gamma$,
explained in Section~\ref{sec:feyn}.
In particular, the recursion is such
that it may be organized in ascending loop order. Also, the graphs are
generated directly in the algebraic representation introduced in
Section~\ref{sec:grep}. This allows their direct evaluation as Feynman
graphs.

More precisely, we shall construct recursively a set of maps
$\Omega^{l,v}:\mathsf{S}(V)\to\mathsf{S}(V)^{\otimesv}$ indexed
by integers $l$ and $v$ such that the following theorem holds.

\begin{thm}
\label{thm:main}
Fix integers $l, n\ge 0$, $v\ge 1$ and operator labels
$x_1,\dots,x_n$. Then, $\Omega^{l,
  v}(\phi(x_1)\cdots\phi(x_n))\in\mathsf{S}(V)^{\otimes v}$
corresponds to the weighted sum over all connected graphs with  $l$
loops, $v$  vertices
and $n$ external edges whose endpoints are  labeled by
$x_1,\dots,x_n$,
each with weight being the inverse of its symmetry factor.
\end{thm}

This specializes for $l=0$ to Lemma~10 of \cite{MeOe:npoint}, with
$\Lambda^{v-1}=\Omega^{0,v}$.

We may conclude with the interpretation in terms of Feynman graphs
and $n$-point functions. Denote the $l$-loop and $v$-vertex
contribution to the ensemble $\sigma$ of connected $n$-point functions
by $\sigma^{l,v}$. In particular, the $l$-loop order
contribution $\sigma^l$ to $\sigma$ and $\sigma$ itself are given by
\begin{equation*}
\sigma^l=\sum_{v=0}^\infty \sigma^{l,v},\qquad
\sigma=\sum_{l=0}^\infty \sigma^l .
\end{equation*}
There is only one contribution with zero vertex number. This is the
Feynman propagator contributing to the 2-point function. Hence
$\sigma^{l,v}$ is zero if $v=0$ and $l\neq 0$, while $\sigma^{0,0}$
is non-zero only on $V\otimes V$ and coincides there with the Feynman
propagator. All non-zero vertex number contributions are captured by
the following corollary.

\begin{cor}
\label{cor:loopexpansion}
For $v\ge 1$:
\[
 \sigma^{l,v}=\nu^{\otimes v}\circ\Omega^{l,v} .
\]
\end{cor}

Restricting to the $l=0$ (tree level) contribution recovers
Corollary~18 of \cite{MeOe:npoint}. Note, however, that the
contribution corresponding to the Feynman propagator was missing there
as well as in Theorem~5 of that paper.

The appendix lists all connected graphs without
external edges as weighted contributions to
$\Omega^{l,v}(\mathbf{1})$, for edge number $e=l+v-1\le 3$.


\subsection{Construction and proof}

The proof proceeds in a manner very analogous to the proof in
\cite{MeOe:npoint}. Indeed, each intermediate lemma in this section
specializes to a corresponding lemma in Section~IV of that paper when
restricted to the case $l=0$. We do not point this out explicitly in
the following, but refer the reader to that paper for comparison.

In order to construct $\Omega^{l,v}$ we introduce certain
auxiliary maps.
Using the component-wise product in $\mathsf{S}(V)^{\otimesv}$, we may view
the elements
$R_{i,j}$, defined by equations (\ref{eq:Rij}) and (\ref{eq:Rii}),
as operators on this
space by multiplication. In particular, these elements are used to
define the following maps:
\begin{itemize}
\item
$T_i:\mathsf{S}(V)^{\otimesv}\to\mathsf{S}(V)^{\otimesv}$, with $1\le i\le
  v$, as the operator $R_{i,i}$ together with the factor
  $1/2$:
\begin{equation}
T_i:=\frac{1}{2}R_{i,i}\,.
\label{eq:T}
\end{equation}
\item
$Q_i:\mathsf{S}(V)^{\otimesv}\to \mathsf{S}(V)^{\otimes{v+1}}$, with $1\le i\le
  v$, given by the composition of $R_{i,i+1}$ with the
  coproduct applied to the $i^{\mbox{\tiny{th}}}$ component of
  $\mathsf{S}(V)^{\otimesv}$, i.e. $\cop_i:=
  \id^{\otimes{i-1}}\otimes\cop\otimes\id^{\otimes{v-i}}:
  \mathsf{S}(V)^{\otimesv}\to\mathsf{S}(V)^{\otimes{v+1}}$,
  together with a factor of $1/2$:
\begin{equation}
Q_i := \frac{1}{2} R_{i,i+1}\circ\cop_i .
\label{eq:Q}
\end{equation} 
\end{itemize}

The map $T_i$ given by (\ref{eq:T}), endows the
$i^{\mbox{\tiny{th}}}$ vertex of a vertex ordered graph with a
self-loop together with a factor $1/2$. The latter is the inverse of
the edge symmetry factor of a single self-loop (see
Lemma~\ref{lem:edgesymfac}).
The action of the map $Q_i$
given by (\ref{eq:Q}) is less simple. Consider the coproduct $\cop_i$
applied to the
$i^{\mbox{\tiny{th}}}$ component of $\mathsf{S}(V)^{\otimes v}$.
Recalling the formula (\ref{eq:coproduct}), we
see that $\cop_i$ converts a graph with $v$ vertices into a sum
over graphs with $v+1$ vertices by \emph{splitting} the
$i^{\mbox{\tiny{th}}}$ vertex into two in all possible ways. That is,
the $i^{\mbox{\tiny{th}}}$ vertex is replaced by two vertices
(numbered $i$ and $i+1$) and the edges ending on it, (considered as
distinguishable)
are distributed between the two new vertices in all possible ways.
Note that the two new vertices are distinguished due to the ordering
of the tensor factors. Thus, to obtain the corresponding
operation for unordered graphs we need to divide by a factor of $2$.
This factor corresponds to the two different relative orderings of the
new vertices with which each unordered configuration occurs.
The only exception to this is the case when the split vertex has no
edges at all. No overcounting happens in this case.
The meaning of the map $Q_i$ given by (\ref{eq:Q})
becomes clear now in terms of graphs. Namely, it splits the
$i^{\mbox{\tiny{th}}}$ vertex into two and subsequently reconnects the
two new vertices with an edge.  Dividing by two compensates for the
double counting as described above if we are interested in unordered
graphs (assuming
the set of endings of edges of the split vertex is not empty). 

We remark that the maps $T_i$ increase both the loop and edge
numbers of a graph by one unit, leaving the vertex number invariant,
while the maps $Q_i$ increase both the edge and vertex numbers by
one unit, leaving the loop number invariant.

We use the maps $T_i$ and $Q_i$, given by equations
(\ref{eq:T}) and (\ref{eq:Q}), respectively, to define recursively
maps  $\Omega^{l,v} :\mathsf{S}(V)\to\mathsf{S}(V)^{\otimesv}$ for
$l\ge 0$ and for $v\ge 1$ as follows:
\begin{align}
\Omega^{0,1} & := \id\,, \nonumber\\
\Omega^{l,v} & :=
\frac{1}{l+v-1}\left(\sum_{i=1}^{v-1}Q_i \circ
\Omega^{l,v-1}+\sum_{i=1}^{v}
T_i\circ\Omega^{l-1,v}\right)\,.
 \label{eq:recomega}
\end{align}

Note that in the recursion equation above the $T$ and $Q$-
summands do not appear when $l=0$ or when $v=1$,
respectively. Figure \ref{fig:table} shows the recursive dependencies
of $\Omega^{l,v}$ for different $l$, $v$ with
$l+v\le 4$.


\begin{figure}
\begin{center}
\input{figures/table.eepic}
\end{center}
\caption{Recursive dependencies of the maps
$\Omega^{l,v}$ up to order $l+v\le 4$. The right
  directed arrows correspond to $T_i$ maps while the left directed
  ones correspond  to $Q_i$ maps.}
\label{fig:table}
\end{figure}


We notice that $\Omega^{l,v}$ satisfies the following
factorization property:
\begin{lem}
\label{lem:omegafac}
Fix integers $l,n, m\ge 0$, $v\ge 1$ and operator labels
$x_1$, $\dots$, $x_n$, $y_1$, $\dots$,
$y_m$. Then,
$\Omega^{l,v}$ satisfies the factorization property
\begin{multline}\label{eq:facomega2}
\Omega^{l,v}(\phi(x_1)\cdots\phi(x_n)\phi(y_1)\cdots\phi(y_m))=\\
 \Omega^{l,v}(\phi(x_1)\cdots\phi(x_n))\cdot
 \cop^{v-1}(\phi(y_1)\cdots\phi(y_m)) .
\end{multline}
\end{lem}
\begin{proof}
This follows from the multiplicativity of the coproduct
and the recursive definition (\ref{eq:recomega}), noticing that each
time the vertex number increases by one, one coproduct is applied as
part of the operator $Q_i$.
\end{proof}

We now turn to the proof of Theorem~\ref{thm:main}. We begin with
weaker lemmas, increasing their strength stepwise until reaching the
desired result.

\begin{lem}
\label{lem:allgraphs}
Fix integers $l,n\ge 0$, $v\ge 1$ as well as field
operator labels
$x_1,\dots,x_n$.
(a) $\Omega^{l,v}(\phi(x_1)\cdots\phi(x_n))$
corresponds  to a weighted sum of  connected graphs with
$l$ loops, $v$ vertices and $n$ external edges whose endpoints
are labeled by
$x_1,\dots,x_n$. (b) Any connected graph with  $l$
loops, $v$
vertices and the given  external edges occurs
in $\Omega^{l,v}(\phi(x_1)\cdots\phi(x_n))$ with some
positive weight.
\end{lem}
\begin{proof}
First, it is clear that $\Omega^{0,1}(\phi(x_1)\cdots\phi(x_n))$
corresponds to the connected graph with one single vertex with no
self-loops and the external edges whose endpoints are
labeled by $x_1,\dots,x_n$. Moreover,
$\Omega^{l,v}(\phi(x_1)\cdots\phi(x_n))$ is generated from
this by sums
of multiple applications of the maps $T_i$ and  $Q_i$ with
scalar factors according to the recursion formula
(\ref{eq:recomega}). Both $T_i$ and $Q_i$ convert a
term corresponding to a connected graph to a sum over terms
corresponding to connected graphs. Thus,
$\Omega^{l,v}(\phi(x_1)\cdots\phi(x_n))$ is a sum of terms
each of which
corresponds to a connected graph (with some weight). Second, the fact
that every graph contained in
$\Omega^{l,v}(\phi(x_1)\cdots\phi(x_n))$ has $l$ loops and
$v$ vertices follows from  noticing that the maps $T_i$
increase the loop number  by one unit, while the vertex number remains
fixed, and the maps $Q_i$ increase the vertex number by one unit,
leaving the loop number  unchanged. This concludes the proof of (a).

To prove (b) we proceed by induction on the internal edge number
$e=l+v-1$ (recall Lemma~\ref{lem:loopnumber}). The result
is evidently valid for $e=0$, corresponding to $l=0$ and
$v=1$. We assume the result holds for $e-1$. Let $\gamma$
denote a graph with $l$ loops and $v$ vertices so that
$l+v-1=e$. We show that it is generated by applying the
maps $T_i$ or $Q_i$ to graphs contained in
$\Omega^{l-1,v}(\phi(x_1)\cdots\phi(x_n))$ or in
$\Omega^{l,v-1}(\phi(x_1)\cdots\phi(x_n))$,
respectively. Since both $T_i$ and $Q_i$ produce graphs with
positive weight from graphs with  positive weight, the weight of a
graph $\gamma$  occurring in $\Omega^{l,v}$, being given by a
sum over positive contributions according to formula
(\ref{eq:recomega}), is positive. Now, suppose the graph $\gamma$ has
at least one vertex with one or more self-loops. Let this vertex
occupy the $i^{\mbox{\tiny{th}}}$ position, for instance.   Shrinking
one of these self-loops yields a graph that corresponds
by assumption to a term in
$\Omega^{l-1, v}(\phi(x_1)\cdots\phi(x_n))$ with some
positive weight so that applying the map $T_i$ to the vertex $i$
produces the graph $\gamma$ with (positive) weight. Thus, by  formula
(\ref{eq:recomega}) the  graph $\gamma$ occurs in
$\Omega^{l,v}$. Finally, suppose the  graph $\gamma$ does not
contain vertices with self-loops. Choose an arbitrary internal
edge. Shrinking this edge and
fusing the vertices it connects yields a graph that corresponds
by assumption to a term in
$\Omega^{l, v-1}(\phi(x_1)\cdots\phi(x_n))$. Say, the
fused vertex has position $i$. Applying $Q_i$ to this term will
yield a sum over terms one of which will correspond to the
original. By the recursive definition of
$\Omega^{l,v}(\phi(x_1)\cdots\phi(x_n))$ it thus contains
this term with
positive weight. This completes the proof of (b).
\end{proof}

What remains in order to prove Theorem~\ref{thm:main} is to show
that the term corresponding to each graph  has weight given exactly by
the inverse of its symmetry factor. We start with a more
restricted result.
\begin{lem}
\label{lem:weightextedges}
Fix integers  $l\ge0$, $v\ge 1$ and $n\ge v$ as well
as field operator
labels $x_1,\dots,x_n$. Consider a connected graph $\gamma$ with
$l$ loops, $v$ vertices, $n$ external
edges whose endpoints are labeled by $x_1,\dots,x_n$ and
the property
that each vertex has
at least one external edge ending on it. Then, the term in
$\Omega^{l, v}(\phi(x_1)\cdots\phi(x_n))$ corresponding to
that graph has
weight given by the inverse of its symmetry factor $S^\gamma$.
\end{lem}
\begin{proof}
We proceed by induction on the number of internal edges
$e$. Clearly, the
statement is true for $e=0$ so that we assume it  holds for a
general number of internal edges $e-1$. Let $\gamma$ be a
connected graph with $e$ internal edges. Let $l$  be its loop
number and let $v$ be
its vertex number. By Lemma~\ref{lem:allgraphs}, this graph  occurs in
$\Omega^{l, v}(\phi(x_1)\cdots\phi(x_n))$ with positive
weight $\alpha$. We proceed to show that
$\alpha=1/S^\gamma$. We pick an ordering of the vertices and also
order the set of pairs of vertices which are connected by at least one
edge. Denote the number of self-loops of the vertex $i$ by
$p_i$, with $1\le i\lev$. Denote the number of edges connecting
the pair $j$ of vertices by $q_j$, with $1\le j\le t$, where
$t$ is the total number of connected pairs of vertices. By
Lemma~\ref{lem:edgesymfac} the edge symmetry factor
of $\gamma$ is given by
$S^\gamma_{\text{edge}}=(\prod_{i=1}^v\, 2^{p_i}\cdot
p_i!)(\prod_{j=1}^t\,q_j!)$ with $e=\sum_{i=1}^v p_i+
\sum_{j=1}^t q_j$. Since the graph $\gamma$ has the property that each
vertex has at least one external edge, its vertices are distinguishable
and it has no non-trivial vertex
symmetries: $S^\gamma_{\text{vertex}}=1$ and
$S_{\text{edge}}^\gamma=S^\gamma$ (as any symmetry is an edge
symmetry). We check from which graphs
with $e-1$ internal edges $\gamma$ is
generated by the recursion formula (\ref{eq:recomega}) and how
many times it is generated. It turns out that we can think of each
internal edge of $\gamma$ as contributing with a factor of
$1/(e\cdot S^\gamma)$ as follows:

(i) Consider the   $i^{\mbox{\tiny{th}}}$ vertex of $\gamma$
endowed with $p_i$ self-loops. Shrinking one of these self-loops
yields a graph $\gamma'$ whose $i^{\mbox{\tiny{th}}}$ vertex has
$p_i-1$ self-loops. Consequently, by Lemma~\ref{lem:edgesymfac}, the
symmetry factor of $\gamma'$ is related to that of $\gamma$ via
$S^{\gamma'}=S^\gamma/(2 p_i)$.  By assumption, the
graph $\gamma'$ corresponds to a term in
$\Omega^{l-1, v}(\phi(x_1)\cdots\phi(x_n))$ which occurs with
weight given by the inverse of its symmetry factor:
$1/{S^{\gamma'}}= 2 p_i/S^\gamma$. Applying the map
$T_i$, which carries the factor $1/2$, to the vertex $i$ of
$\gamma'$ produces the graph $\gamma$ from the graph $\gamma'$ exactly
with factor $p_i/S^\gamma$. Thus, the contribution to
(\ref{eq:recomega}) is $p_i/(e\cdot S^\gamma)$. Distributing
this factor between the $p_i$ edges considered yields
$1/(e\cdot S^\gamma)$ for each edge considered.

(ii) Consider the $j^{\mbox{\tiny{th}}}$ pair of vertices of
$\gamma$ connected by $q_j$ edges. We assume now the indices of the
vertices forming this pair to be consecutive, given by $k$ and
$k+1$.\footnote{Note that this merely amounts to a particular vertex ordering
of the graph $\gamma$. Since $\gamma$ is a priori
unordered this does not imply any loss of generality.}
Shrinking one of the edges and
fusing the vertices it connects yields a graph $\gamma''$ whose fused
vertex has $r:= p_k+p_{k+1}+q_j-1$ self-loops.  Consequently, by
Lemma~\ref{lem:edgesymfac}, the symmetry factor  of $\gamma''$ is
related to that of $\gamma$ as follows:
\[
\frac{1}{2^r}\frac{1}{r!}S^{\gamma''}
=\frac{1}{2^{p_k}p_k!}\frac{1}{2^{p_{k+1}}p_{k+1}!}\frac{1}{q_j!}
S^\gamma .
\]
By assumption, the graph $\gamma''$ corresponds to a term
in $\Omega^{l, v-1}(\phi(x_1)\cdots\phi(x_n))$ which occurs
with weight given by the inverse of its symmetry factor, i.e.,
\begin{equation}
\frac{1}{S^{\gamma''}}
=\frac{p_k!\,p_{k+1}!\,q_j!}{r!}\cdot\frac{1}{2^{q_j-1}S^\gamma} .
\label{eq:symweight}
\end{equation}
The map $Q_k$, when applied to the fused vertex, produces a pair of
vertices occupying the positions $k$ and $k+1$, distributes the $2r$
endings of edges between the two vertices in all possible ways  and
attaches them together by an edge. The action of $Q_k$ on the fused
vertex $k$ (leaving out external edges) reads explicitly as 
\begin{align}\label{eq:QRjj1}
Q_kR_{k,k}^r & 
 =
 \frac{1}{2}R_{k,k+1}(R_{k,k}+2R_{k,k+1}+R_{k+1,k+1})^r\\
 \label{eq:QRjj2}
& =  \sum_{a=0}^r\sum_{b=0}^a \left( \begin{array}{c}
r\\
a \end{array} \right)\left( \begin{array}{c}
a\\
b \end{array} \right)
2^{a-b-1}R_{k,k}^{r-a}R_{k,k+1}^{a-b+1}R_{k+1,k+1}^b\,.
\end{align}   
Taking into account the external edges,
there are two  terms in equation (\ref{eq:QRjj2}) corresponding to the
graph $\gamma$:  one with   $r-a=p_k$ and $b=p_{k+1}$ and one with
$r-a=p_{k+1}$ and $b=p_k$. The sum of the coefficients of these two
contributions is
\begin{equation}
 2^{q_j-1}\,\frac{r!}{p_k!\,p_{k+1}!\,(q_j-1)!}.
\label{eq:combweight}
\end{equation}
Multiplying (\ref{eq:symweight}) with (\ref{eq:combweight}), we see
that $Q_j$ produces $\gamma$ from $\gamma''$ exactly with a factor
$q_j/S^\gamma$ and the contribution to
(\ref{eq:recomega}) is $q_j/(e\cdot S^\gamma)$. In other
words, we get a factor of $1/(e\cdot S^\gamma)$ for each of
the $q_j$ edges considered.

Since each of the $e=l+v-1$ internal edges contributes with a
factor of
$1/(e\cdot S^\gamma)$ to the weight of the graph $\gamma$,
the overall contribution is exactly $1/S^\gamma$. This
completes the proof.
\end{proof}

To complete the proof of  Theorem~\ref{thm:main}, we show that the
term in $\Omega^{l, v}(\phi(x_1)\cdots\phi(x_n))$
corresponding to a connected graph $\gamma$  with  $l$ loops,
$v$ vertices and 
external edges whose endpoints are labeled by $x_1,\dots,x_n$, has
weight given by $1/S^\gamma$. If $\gamma$ has external edges
attached to every one of its vertices we
simply recall Lemma~\ref{lem:weightextedges}. Thus, we may now assume
that $\gamma$ has $m$ vertices to which no external leg is
attached. Consider a graph
$\gamma'$ which is constructed from $\gamma$ by attaching an external
edge to every vertex without external edges, choosing arbitrary but
fixed labels $y_1,\dots,y_m$ for the endpoints of external edges in
the process.
By Lemma~\ref{lem:weightextedges}, the graph
$\gamma'$ occurs in the
term on the left hand side of equation (\ref{eq:facomega2}) with
weight $1/S^{\gamma'}$. By Lemma~\ref{lem:allgraphs},
the graph $\gamma$ occurs in the
first factor on the right hand side with some non-zero weight, say
$\alpha$.
Every summand of $\cop^{v-1}(\phi(y_1)\cdots\phi(y_m))$ (recall
formula (\ref{eq:copk}))
which places the endpoints of external edges at the designated
vertices of $\gamma$
to produce $\gamma'$ contributes to the weight of $\gamma'$ in terms
of that of $\gamma$. Any different ways this can happen define a vertex
symmetry of $\gamma$. Furthermore, $\gamma$ can have no more than
these vertex symmetries, since its vertices that already carry external edges
are distinguishable and thus held fixed under any symmetry.
Therefore, using Lemma~\ref{lem:omegafac}
we obtain the formula $1/S^{\gamma'}=\alpha\cdot
S^\gamma_{\text{vertex}}$ by extracting the weights from the
corresponding terms in equation (\ref{eq:facomega2}). Moreover,
$S^{\gamma'}=S^{\gamma'}_{\text{edge}}=S^{\gamma}_{\text{edge}}$.
Thus, using $S^\gamma=S^{\gamma}_{\text{vertex}}\cdot
S^{\gamma}_{\text{edge}}\,$ (Lemma~\ref{lem:sym}), we find
$\alpha=1/S^\gamma$. This completes the proof.





