\section{\normalsize Introduction}\setcounter{equation}{0}
All graphs considered here are finite, simple and connected. Undefined terminology and notation may be referred to \cite{D-I}.
Let $G=(V_G,E_G)$ be a simple undirected graph with $n$ vertices. $G-v$, $G-uv$ denote the graph obtained from $G$ by deleting vertex $v \in V_G$, or edge
$uv \in E_G$, respectively (this notation is naturally extended if more than one vertex or edge is deleted). Similarly,
$G+uv$ is obtained from $G$ by adding an edge $uv \not\in E_G$. For $v\in V_G$, let
$N_G(v)$ (or $N(v)$ for short) denote the set of all the adjacent vertices of $v$ in $G$ and $d_G(v)=|N_G(v)|$, and $\dist_G(u,v)$ is the distance between $u$ and $v$. For an edge subset $E'$ of $G$, denoted by $G[E']$ the subgraph induced by $E'$.
A cut edge in a connected graph $G$ is an edge whose deletion breaks the graph into two components. Let $\mathscr{G}_n^k$ be the set of all $n$-vertex graphs, each of which contains $k$ cut edges.

Let $A(G)$ be the adjacency matrix of a graph $G$ with $\lambda_1(G),\lambda_2(G),\dots,\lambda_n(G)$ being its eigenvalues in non-increasing order. The number $\sum_{i=1}^n\lambda_i^k(G)\, (k=0,1,\dots,n-1)$ is called the $k$th spectral moment of $G$, denoted by $S_k(G)$. Let $S(G)=(S_0(G), S_1(G), \dots, S_{n-1}(G))$ be the sequence of spectral moments of $G$. For two graphs $G_1, G_2$, we shall write $G_1=_sG_2$ if $S_i(G_1)=S_i(G_2)$ for $i=0,1,\dots,n-1$. Similarly, we have $G_1\prec_sG_2\, (G_1$ comes before $G_2$  in an $S$-order) if for some $k\, (1\leq k\leq {n-1})$, we have  $S_i(G_1)=S_i(G_2)\, (i=0,1,\dots,k-1)$  and $S_k(G_1)<S_k(G_2)$. We shall also write $G_1\preceq_sG_2$ if $G_1\prec_sG_2$ or $G_1=_sG_2$.  $S$-order has been used in producing graph catalogs (see \cite{C-G}), and for a more general setting of spectral moments one may be referred to \cite{C-R-S1}.

Investigation on $S$-order of graphs attracts more and more researchers' attention. Cvetkovi\'c and Rowlinson \cite{C-R-S3} studied
the $S$-order of trees and unicyclic graphs and characterized the first and the last graphs, in an $S$-order,
of all trees and all unicyclic graph with given girth, respectively. Chen, Liu and Liu \cite{C-L-L} studied the lexicographic ordering
by spectral moments ($S$-order) of unicyclic graph with a given girth. Wu and Fan \cite{D-F} determined the first
and the last graphs, in an $S$-order, of all unicyclic graphs and bicyclic graphs, respectively. Pan et al. \cite{X-F-P}
gave the first $\sum_{k=1}^{\lfloor\frac{n-1}{3}\rfloor}(\lfloor\frac{n-k-1}{2}\rfloor-k+1)$ graphs apart from an $n$-vertex path, in an $S$-order, of all trees with $n$ vertices. Wu and Liu \cite{D-M} determined the last $\lfloor\frac{d}{2}\rfloor+1$, in an $S$-order,
among all $n$-vertex trees of diameter $d\, (4 \le d \le n-3)$. Pan et al. \cite{B-Z1} identified the
last and the second last graphs, in an $S$-order, of quasi-trees. Hu, Li and Zhang \cite{Li-H} studied the spectral moments of graphs with given clique number and chromatic number, respectively. Li and Song \cite{Li-S} identified the last $n$-vertex tree with a given degree sequence in an $S$-order. Consequently, the last trees in an $S$-order in the sets of all trees of order $n$ with the largest degree, the leaves number, the independence number and the matching number was also determined, respectively.

In light of the information available from the related results on the spectral moments of graphs, it is natural to consider this problem on some other class of graphs, and the connected graphs with $k$ cut edges are a reasonable starting point for such a investigation. The $n$-vertex connected graphs with $k$ cut edges have been considered in different fields  \cite{B-Z10,2,3,4}, whereas to our best knowledge, the spectral moments of graphs in $\mathscr{G}_n^k$ were, so far, not considered. Here, we identified the first, the second, the last and the second
last graphs, in an $S$-order, among $\mathscr{G}_n^k$, respectively.

Throughout the text we denote by $P_n, K_{1,n-1}, C_n$ and $K_n$ the path, star, cycle and complete graph on $n$ vertices, respectively. Let $K_{1,n-1}^*$ be a graph obtained from a star $K_{1,n-1}$ by attaching a leaf to one leaf of $K_{1,n-1}$, $U_n$ be a graph obtained from $C_{n-1}$ by attaching a leaf to one vertex of $C_{n-1}$, and $B_4, B_5$ be two graphs  obtained from two cycle $C_3, C_3'$ of length 3 by identifying one edge of  $C_3$ with one edge of $C_3'$ and identifying one vertex of $C_3$ with one vertex  of $C_3'$, respectively; see Fig. 1.
\begin{figure}[h!]
\begin{center}

\psfrag{a}{$u_1$}
\psfrag{b}{$u_2$}\psfrag{e}{$K_{a_1}$}
\psfrag{f}{$K_{a_2}$}
\psfrag{g}{$K_{a_{k-1}}$}
\psfrag{h}{$K_{a_k}$}
\psfrag{c}{$u_{k-1}$}
\psfrag{d}{$u_k$}
\psfrag{x}{$u_0$}
\psfrag{y}{$v_0$}
\psfrag{A}{$K_{a_0}$}
\psfrag{9}{$K(a_0,\{a_1, a_2, \dots, a_k\})$}
\psfrag{1}{$B_4$}
\psfrag{2}{$B_5$}
\psfrag{3}{$K_6^1$}
\psfrag{4}{$K_6^2$}
\psfrag{5}{$K_6^3$}
\psfrag{6}{$P_6^1$}
\psfrag{7}{$P_6^2$}
\psfrag{8}{$P_6^3$}
\includegraphics[width=120mm]{fig1.eps}\\
\caption{Graphs $B_4, B_5, K_6^1, K_6^2, K_6^3, P_6^1, P_6^2, P_6^3$ and $K(a_0,\{a_1, a_2, \dots, a_k\}).$
\end{center}
\end{figure}

The graph $K_n^k$ is an $n$-vertex graph obtained by attaching $k$ pendant vertices to one vertex of $K_{n-k}$. The graph $P_n^k$ is a graph obtained by identifying one end-vertex of $P_{k+1}$ with one vertex of $C_{n-k}$. For example, for $n=6, K_6^0=K_6, K_6^5  $ is a star, $P_6^0=C_6$ and $K_6^1, K_6^2, K_6^3, P_6^1,  P_6^2, P_6^3$ are depicted in Fig. 1. In general, $K_n^0=K_n, K_n^{n-1}$ is star $K_{1,n-1}$, $K_n^{n-2}\cong K_n^{n-1}$ and $P_n^0=C_n$. Let  $K(a_0,\{a_1,a_2,\dots,a_k\})$ be a graph obtained from $K_{1,k}$ by replacing each $u_i\in V_{K_{1,k}}$ by a clique $K_{a_i}\, (a_i\geq1, i=0,1,2,\dots,k)$; see Fig. 1. Denote
$$
 \mathscr{K}_n^k=\left\{K(a_0,\{a_1,a_2,\dots,a_k\}):a_i\geq1(0\leq i\leq k),\,\sum_{i=0}^ka_i=n\right\}.
$$
Let $F$ be a graph. An $F$-subgraph of $G$ is a subgraph of $G$ which is isomorphic to the graph $F$. Let $\phi_{G}(F)$ (or $\phi(F)$) be the number of all $F$-subgraph of $G$.
\begin{lem} {\rm(see \cite{C-R-S2})}
The $k$th spectral moment of $G$ is equal to the number of closed walks of length $k$.
\end{lem}
\begin{lem}
For every graph $G$, we have
\begin{wst}
\item[{\rm (i)}] $S_4(G)=2\phi(P_2)+4\phi(P_3)+8\phi(C_4)$ {\rm(see \cite{C-G});}
\item[{\rm (ii)}] $S_5(G)=30\phi(C_3)+10\phi(U_4)+10\phi(C_5)$ {\rm(see\cite{D-M});}
\item[{\rm (iii)}]
     $S_6(G)=2\phi(P_2)+12\phi(P_3)+6\phi(P_4)+12\phi(K_{1,3})+12\phi(U_5)+36\phi(B_4)+24\phi(B_5)+24\phi(C_3)+48\phi(C_4)+12\phi(C_6)
\, ${\rm(see\cite {C-L-L}).}
\end{wst}
\end{lem}
\begin{lem}[\cite{C-R-S2}]
Given a connected graph $G$, $S_0(G)=n, S_1(G)=l, S_2(G)=2m, S_3(G)=6t$, where $n, l, m, t$ denote the number of vertices, the number of loops, the number of edges and the number of triangles contained in $G$, respectively.
\end{lem}
\begin{lem}[\cite{C-R-S3}]\label{lem4}
In an $S$-order of the $n$-vertex unicyclic graphs with girth $g$, the first graph is $U_n^g$ which is obtained by the coalescence of a cycle $C_g$  with
a path $P_{n-g+1}$ at one of its end-vertices.
\end{lem}
\section{\normalsize The last and the second last graphs in an $S$-order among $\mathscr{G}_n^k$}\setcounter{equation}{0}
In this section, we will determine the last two graphs, in an $S$-order, among $\mathscr{G}_n^k$.
Let $\Bbb E=\{e_1,e_2,\dots,e_k\}$ be the set of the cut edges of $G\in\mathscr{G}_n^k$. Note that $S_2(G)=2|E_G|$, hence $S_2(G+e)>S_2(G)$. By Lemma 1.3, in order to determine the last graph in an $S$-order among $\mathscr{G}_n^k$, it suffices to choose graph $G\in\mathscr{G}_n^k\emph{}$ such that its $S_2(G)$ is as large as possible. So we can have the following assumption throughout this section.

\vspace{2mm}\noindent {\bf Assumption 0.}  Each component of $G-\Bbb E$ is a clique.

\begin{thm}
Of all the connected graphs with $n$ vertices and $k$ cut edges, the last graph in an $S$-order is obtained uniquely at $K_n^k$.
\end{thm}

\begin{proof}

If $k=0$, then by Assumption 0 we have $\mathscr{G}_n^0=\{K_n\}$, our result holds immediately. Therefore we may assume that $k\geq1$. Again by Assumption 0, we can denote the components of $G-\Bbb E$ by $K_{a_0},K_{a_1},\dots,K_{a_k},\, a_0+a_1+\dots+a_k=n$. Assume, without loss of generality, that $a_0\geq a_1\geq a_2\geq\dots\geq a_k\geq1$.

Let $V_i=\{v\in V_{K_{a_i}}\!:\, v$ is an end-vertex of a cut edge of $G$\}. Choose $G\in\mathscr{G}_n^k$  such that $G$ is as large as possible under the order $\preceq_s$. In order to complete the proof, it suffices to show the following facts.

\vspace{2mm}\noindent {\bf Fact 1}.  $|V_i|=1$ for $i=0,1,2,\ldots, k.$
\begin{proof}
Suppose to the contrary that there exists $i\in \{0,1,2,\ldots, k\}$ such that $|V_i|>1$. Let $u,u' \in V_{a_i}$, both $u$ and $u'$ are end-vertices of the cut edges of $G$. Denote  $N_G(u)\backslash N_{K_{a_i}}(u)=\{w_1,w_2,\dots,w_s\}$ and $N_G(u')\backslash N_{K_{a_i}}(u')=\{z_1,z_2,\dots,z_l\}$. It is routine to check that  $s\geq1,\, l\geq 1$. Let
  $$G^*=G-\{u'z_1,u'z_2,\dots,u'z_l\}+\{uz_1,uz_2,\dots,uz_l\},
  $$
  then  $G^* \in \mathscr{G}_n^k$.

On the one hand, $S_i(G)=S_i(G^*)$ for $i=0, 1, 2, 3.$ On the other hand, $\phi_G(P_2)=\phi_{G^*}(P_2),  \phi_G(C_4)=\phi_{G^*}(C_4)$, hence by Lemma 1.2(i),
\begin{eqnarray*}
 S_4(G)-S_4(G^*)  = 4(\phi_G(P_3)-\phi_{G^*}(P_3))=4\left({s\choose 2}+{l\choose 2}-{s+l\choose 2}\right)=-4sl<0.
  \end{eqnarray*}
which implies that $G\prec_sG^*$, a contradiction. Therefore $|V_i|=1$ for $0\leq i \leq k $.
\end{proof}

By Fact 1, we can assume that $V_i=\{u_i\}$ for $i=0,1,2,\ldots, k$.

\vspace{2mm}\noindent {\bf Fact 2}.  $G\in \mathscr{K}_n^k$.\vspace{2mm}

\begin{proof}
If not, then there exists a cut edge $u_0u_i\in \Bbb E$ such that $u_i$ is an end-vertex of another cut edge(s). Let
$$
|N_G(u_i)\setminus (N_{K_{a_i}}(u_i)\cup \{u_0\})|=l, \ \ \ |N_G(u_0)\setminus (N_{K_{a_0}}(u_0)\cup \{u_i\})|=s.
$$
It is straightforward to check that $l\ge 1$ and $s\ge 0.$

First consider that $s\geq1$. In this case, let
$$
    G^*=G-\{u_iz: \, z\in N_G(u_i)\setminus (N_{K_{a_i}}(u_i)\cup \{u_0\})\}+\{u_0z: \, z\in N_G(u_i)\setminus (N_{K_{a_i}}(u_i)\cup \{u_0\})\}.
$$
It is easy to see that $G^*\in \mathscr{G}_n^k$. Note that $S_i(G)=S_i(G^*)$ for $i=0,1,2,3$ and $\phi_G(P_2)=\phi_{G^*}(P_2)$, $\phi_G(C_4)=\phi_{G^*}(C_4)$, hence
    $$
    S_4(G)-S_4(G^*)  = 4(\phi_G(P_3)-\phi_{G^*}(P_3))=4(l(a_i-1)-l(a_0-1)-ls)=4l(a_i-a_0-s)<0,
    $$
which implies that $G\prec_sG^*$, a contradiction.

Now consider that $s=0$. In this case, there exists a cut edge $u_iu_j\in \Bbb E$ such that $u_j$ is an end-vertex of another cut edge(s).
Let
$
|N_G(u_j)\setminus (N_{K_{a_j}}(u_j)\cup \{u_i\})|=p.
$
It is straightforward to check that $p\ge 1$. Let
\begin{eqnarray*}
    G^*&=&G-\{u_jz: \, z\in N_G(u_j)\setminus (N_{K_{a_j}}(u_j)\cup \{u_i\})\}+\{u_0z: \, z\in N_G(u_j)\setminus (N_{K_{a_j}}(u_j)\cup \{u_i\})\}\\
       && -\{u_iw: \, w\in N_G(u_i)\setminus (N_{K_{a_i}}(u_i)\cup \{u_0\})\}+\{u_0w: \, w\in N_G(u_i)\setminus (N_{K_{a_i}}(u_i)\cup \{u_0\})\}.
\end{eqnarray*}
It is easy to see that $G^*\in \mathscr{G}_n^k$. Note that $S_i(G)=S_i(G^*)$, $i=0,1,2,3$ and $\phi_G(P_2)=\phi_{G^*}(P_2)$, $\phi_G(C_4)=\phi_{G^*}(C_4)$. Hence,
\begin{eqnarray*}
S_4(G)-S_4(G^*)  &=&  4(\phi_G(P_3)-\phi_{G^*}(P_3))\\
                 &=& 4l(a_i-1)+p(a_j-1)-4p(l-1)-4p-4(l+p)(a_0-1)\\
                 &=&4[l(a_i-a_0)+p(a_j-a_0)-pl]<0.
\end{eqnarray*}
The last inequality follows from $a_i\le a_0, a_j\le a_0$ and $pl>0.$ Hence, we obtain that $G\prec_sG^*$, a contradiction. Therefore $G\in \mathscr{K}_n^k$.
\end{proof}

By Fact 2, we can assume that $u_0u_j\in \Bbb E$, $1\leq j \leq k$.

\vspace{2mm}\noindent {\bf Fact 3}. $a_1=a_2=\cdots=a_k=1$.
\begin{proof}
Assume to the contrary that there exists a $j\in \{1,2,\ldots,k\}$ such that $a_j>1$. By Fact 2, we have $G=K(a_0,\{a_1,\ldots,a_{j-1},a_j, a_{j+1},\ldots,a_k\})$. Now we consider $G^*=K(a_0+a_j-1,\{a_1,\ldots,a_{j-1},1, a_{j+1},\linebreak \ldots,a_k\})$. It is easy to see that $G^*\in \mathscr{K}_n^k.$

Note that $S_i(G)=S_i(G^*),\,i=0,1$ and
$$
  S_2(G)-S_2(G^*)=2(a_j-1)-2(a_j-1)a_0=2(a_j-1)(1-a_0)<0,
$$
i.e., $ G\prec_s G^*$, a contradiction. Therefore $a_j=1$ for $j=1,2,\ldots, k$.
 \end{proof}
In the view of Fact 3, we have $a_0=n-k$. Hence, $G=K(n-k,\{1,1,\ldots,1\})$, i.e., $G\cong K_n^k$, as desired.
\end{proof}

In the rest of this section, we are to determine last graph in an $S$-order among $\mathscr{G}_n^k\backslash K_n^k$.
Delete an edge, say $xy$, from $K_n$ and denote the resultant graph by $G_1$. Let $G_2$ be a graph obtained from $G_1$ by attaching a pendant vertex to one vertex, say $r$, of $G_1$ with $r\not=x, y$. Let $G_3=K(n-k,\{\underbrace{1,1,\dots,1}_k\})-uw+vw$, where $uw$ is a cut edge and $u, v$ are two different vertices in $V_{K_{n-k}}$.

Based on Lemma 1.3, it is easy to see that among $\mathscr{G}_n^0,$ $K_n$ (resp. $G_1$) is the last (resp. the second last) graph in an $S$-order, while among $\mathscr{G}_n^1$ with $n\ge 5$, based on $S_2(G)$, the second last graph in an $S$-order must be a graph obtained from $K_n^1$ by deleting a non-cut edge, say $e$, from $K_n^1$. Denote the resultant graph by $G'$ if $e$ has a common vertex with the cut edge in $K_n^1$ and by $G_2$ otherwise. Note that $S_i(G_2)=S_i(G')$ for $i=0,1,2,3$ and
$\phi_{G_2}(P_2)=\phi_{G'}(P_2),\, \phi_{G_2}(C_4)=\phi_{G'}(C_4),$ hence by Lemma 1.2(i)
$$
S_4(G')-S_4(G_2)=4(\phi_{G'}(P_3)-\phi_{G_2}(P_3))=-4<0,
$$
i.e., $G'\prec_sG_2$, Hence, among $\mathscr{G}_n^1$ with $n\ge 5$, $G_2$ is the second last graph in an $S$-order. In what follows we only consider $k\geq2$.

\begin{thm}
Among $\mathscr{G}_n^k$ with $2\le k\le n-1$, the second last graph in an $S$-order is obtained uniquely at $G_3$ if $k\in \{2,3,\ldots, n-2\}$ and at $K_{1,n-1}^*$ otherwise, where $G_3$ is defined as above.
\end{thm}
\begin{proof}
Choose $G\in \mathscr{G}_n^k\setminus\{K_n^k\}$ such that it is as large as possible according to $\preceq_s$.
Denote the components of $G-\Bbb E$ by $U_0, U_1, U_2, \ldots, U_k$. We are to show that each of the components is a complete graph. In fact, if there exists a $U_i$ which is not a complete graph, i.e., $U_i$ contains two vertices $x, y$ satisfying $xy\not\in E_{U_i}$. Let $G'=G+xy$. If $G'\not\cong K_n^k$, it is easy to see that $G\prec_s G'$, a contradiction. If $G'\cong K_n^k$, then either $x$ or $y$ is not an end-vertex of a cut edge of $G$. Without loss of generality, assume that  $x$ is not an end-vertex of a cut edge of $G$, delete a cut edge of $G'$ and connect the isolated vertex with $x$ by an edge; denote the resultant graph by $G''$. Then we have $S_0(G)=S_0(G''), S_1(G)=S_1(G'')$ and $S_2(G)<S_2(G'').$ Hence, $G\prec_s G''$, a contradiction. Therefore, we may denote the components of $G-\Bbb E$ by $K_{a_0},K_{a_1},\dots,K_{a_k}$,\, $a_0+a_1+\dots+a_k=n$. Without loss of generality, assume that $a_0\geq a_1\geq a_2\geq\dots\geq a_k\geq1$.

If $a_0=1$, then $G$ is an $n$-vertex tree. By [13, Theorems 3.3 and 3.8], we know the second last tree in an $S$-order among $n$-vertex trees is just $K_{1,n-1}^*$. It is easy to see that $a_0\not=2,$ hence in what follows we consider $a_0\ge 3.$

Let $V_i=\{v\in V_{K_{a_i}}\!:\, v$ is an end-vertex of a cut edge of $G$\}. In order to complete the proof, it suffices to show the following facts.

\vspace{2mm}\noindent {\bf Fact 1}. If $a_0\geq3$, then $|V_0|=2, |V_1|=|V_2|=\cdots=|V_k|=1$.
\begin{proof}
We prove Fact 1 by contradiction. If $|V_0|=|V_1|=|V_2|=\cdots=|V_k|=1$, then without loss of generality assume that $V_i=\{u_i\}$,\, $i=0,1,\ldots, k$.

First we consider $G\in \mathscr{K}_n^k$. Note that $G\in \mathscr{K}_n^k\setminus\{K_n^k\}$, hence $a_1\geq3$; otherwise, $a_1=2$, which implies that $G$ contains at least $k+1$ cut edges, a contradiction. If $a_1>3$, we consider graph $G^*:=K(a_0+1,\{a_1-1, a_2,\ldots, a_k\})$ in $\mathscr{K}_n^k\setminus\{K_n^k\}$.
Note that $S_i(G)=S_i(G^*)$ for $i=0,1$ and $S_2(G)-S_2(G^*)=2(a_1-1-a_0)<0$, hence $G\prec_sG^*$, a contradiction. Therefore $a_1=3$.

If $a_2>1$, we consider graph $G':=K(a_0+a_2-1,\{3, 1,a_3,\ldots, a_k\})\in \mathscr{G}_n^k\backslash K_n^k$. Note that $ S_i(G)=S_i(G')$ for $i=0,1$ and $S_2(G)-S_2(G')=2(a_2-1-(a_2-1)a_0)=2(a_2-1)(1-a_0)<0$, hence $G\prec_s G'$, a contradiction. Therefore, $a_2=1$, whence $a_3=\dots=a_k=1$. Together with $a_1=3$, we have $a_0=n-k-2.$ That is to say, $G\cong K(n-k-2,\{3,1,1,\ldots, 1\}).$

For convenience, let $w_1\in N_{K_{a_0}}(u_0)$ and $N_G(u_1)=\{u_0,v_1,v_2\}.$ Consider
$$
G^*:=G-\{u_1v_1,u_1v_2\}+\{w_1v_1,w_1v_2\},
$$
it is easy to see that $G^*\in\mathscr{G}_n^k\backslash K_n^k$. Note that $S_i(G)=S_i(G^*)$ for $i=0,1,2,3$ and $\phi_G(P_2)=\phi_{G^*}(P_2), \phi_G(C_4)=\phi_{G^*}(C_4)$,
$\phi_G(P_3)-\phi_{G^*}(P_3)=2-2(a_0-1)=2(2-a_0)<0$, hence by Lemma 1.2(i) $S_4(G)<S_4(G^*)$. Thus $G\prec_s G^*$, a contradiction.
Therefore $G\not\in\mathscr{K}_n^k$.

Now we consider the case $G\not\in\mathscr{K}_n^k$. It is easy to see that the edge induced graph $G[\Bbb{E}]$ is a tree which is not isomorphic to $K_{1,k}.$
Hence, partition $V_{G[\Bbb{E}]}$ into $D^0(G[\Bbb{E}])\cup D^1(G[\Bbb{E}])\cup D^2(G[\Bbb{E}])\cup D^3(G[\Bbb{E}])\cup \cdots$, where $D^i(G[\Bbb{E}])=\{u\in V_{G[\Bbb{E}]}: \dist_{G[\Bbb{E}]}(u, u_0)=i\},\, i=0,1,2,3,\ldots.$
It is easy to see that $D^2(G[\Bbb{E}])\not=\emptyset.$

If $D^3(G[\Bbb{E}])\not=\emptyset$, that is to say, there exists $u\in D^2(G[\Bbb{E}])$ such that $d_{G[\Bbb{E}]}(u)\ge 2,$ then choose $u_i$ from $D^1(G[\Bbb{E}])$ such that $u_i$ is adjacent to $u_0$ and $u$. Let $W:=N_{G[\Bbb{E}]}(u_i)\setminus \{u_0\}.$ As $u\in W$, we have $W\not=\emptyset$. Consider
$$
G^*=G-\{u_iw:\, w\in W\}+\{u_0w:\, w\in W\},
$$
then its routine to check that $G^*\in\mathscr{G}_n^k\setminus \{K_n^k\}$. Note that $S_i(G)=S_i(G^*)$ for $i=0, 1, 2,3$ and $\phi_G(P_2)=\phi_{G^*}(P_2), \phi_G(C_4)=\phi_{G^*}(C_4)$, hence by Lemma 1.2(i) we have
$$
  S_4(G)-S_4(G^*) = 4(\phi_G(P_3)-\phi_{G^*}(P_3))=4[(a_i-a_0)-st],
$$
where $s=|W|\ge 1$ and $t=|N_{G[\Bbb{E}]}(u_0)\setminus\{u_i\}|\ge 0$.
Note that $a_i\le a_0$, hence if $a_i<a_0$, then for all $t\ge 0$ we have $(a_i-a_0)-st<0$, which implies that $G\prec_sG^*$, a contradiction. If
$a_i=a_0$, then for all $t\ge 1$ we have $(a_i-a_0)-st<0$, which implies that $G\prec_sG^*$, a contradiction. If $a_i=a_0$ and $t = 0$, then
$G^*\cong G$. Hence, in order to complete the proof, it suffices to consider $D^3(G[\Bbb{E}])=\emptyset$ and $d_{G[\Bbb{E}]}(u_0)>1.$ Furthermore, as $G\not\in \mathscr{K}_n^k$, we have $D^2(G[\Bbb{E}])\not=\emptyset$ and for each $u\in D^2(G[\Bbb{E}])$, $u$ is a leaf of $G[\Bbb{E}]$ (otherwise, $D^3(G[\Bbb{E}])\not=\emptyset,$ a contradiction).

If there exists $u_i\in D^1(G[\Bbb{E}])$ such that $d_{G[\Bbb{E}]}(u_i)\ge 3$, then move $d_{G[\Bbb{E}]}(u_i)-2$ pendant edges to $u_0$ and denote the resultant graph by
$G'$. It is easy to see that $G'\in\mathscr{G}_n^k \setminus \{K_n^k\}.$ Note that $s:=d_{G[\Bbb{E}]}(u_i)-2\ge 1,\, q:=d_{G[\Bbb{E}]}(u_0)-1\ge 1,\, S_i(G)=S_i(G')$ for $ i=0,1,2,3$ and $\phi_G(P_2)=\phi_{G'}(P_2),\phi_G(C_4)=\phi_{G'}(C_4)$, hence by Lemma~1.2(i) we have
\begin{eqnarray}
S_4(G)-S_4(G')    &=& 4(\phi_G(P_3)-\phi_{G'}(P_3))\notag\\
                  &=&  4[s(a_i-1)-s(a_0-1)-s(q-1)]\notag\\
                  &=& 4s(a_i-a_0-q+1).
\end{eqnarray}
If $a_0>a_i$ or $q\geq2$, in the view of (2.1), we obtain that $S_4(G)-S_4(G')<0$, i.e., $G\prec_sG'$, a contradiction. If  $a_0=a_i$ and $q=1$, then it is easy to see $G'\cong G$. Hence, in order to complete the proof, it suffices to consider that, in the edge induced graph $G[\Bbb{E}]$, each of the non-pendant vertices in $D^1(G[\Bbb{E}])$ is of degree 2.

For convenience, let $W=\{u: u\in D^1(G[\Bbb{E}]), d_{G[\Bbb{E}]}(u)=2\}.$ It is easy to see that $W\not=\emptyset.$ If $|W|\ge 2$, choose $u\in W$ such that
its unique neighbor in $G[\Bbb{E}]$ is a leaf, say $u'$. Let $$
G^*=G-uu'+u_0u',
$$
then $G^*\in\mathscr{G}_n^k\setminus\{K_n^k\}$.
Since $S_i(G)=S_i(G^*)$ for $ i=0,1,2,3$ and $\phi_G(P_2)=\phi_{G^*}(P_2),\phi_G(C_4)=\phi_{G^*}(C_4)$,
$$
\phi_G(P_3)-\phi_{G^*}(P_3)=(a_i-1)-(a_0-1)-p=a_i-a_0-p<0,
$$
we have $S_4(G)-S_4(G^*)<0,$ i.e., $G\prec_sG^*$, a contradiction.
Hence, $|W|=1$.

By a similar discussion as in the proof of Fact 3 in Theorem 2.1, we can obtain that $a_0=n-k, a_1=a_2=\ldots=a_k=1$. Note that $a_0\geq 3$, hence $k<n-1$. Assume that $W=\{u\}$ with $N_{G[\Bbb{E}]}(u)=\{u_0, u'\}$, where $u'$ is a pendant vertex in $G[\Bbb{E}]$.
Let $x\in N_{K_{a_0}}(u_0)$. Consider
$
G^*=G-\{uu'\}+\{xu'\},
$
then $G^*\in\mathscr{G}_n^k\setminus\{K_n^k\}$.
Note that $S_i(G)=S_i(G^*)$ for $i=0,1,2,3$,\, $\phi_G(P_2)=\phi_{G^*}(P_2), \phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)=1-(a_0-1)=2-a_0<0$ $(a_0\geq3)$, hence $S_4(G)-S_4(G^*)<0,$ i.e., $G\prec_sG^*$, a contradiction.

If there is a $V_i$ satisfying $|V_i|\geq3$, then choose two distinct vertices $u_i', u_i''$ in $V_i$ and let
$
G^*=G-\{u_i'u:\, u\in N_{G[\Bbb{E}]}(u_i')\}+\{u_i''u:\, u\in N_{G[\Bbb{E}]}(u_i')\}.
$
It is easy to see that $G^*\in\mathscr{G}_n^k\setminus\{K_n^k\}$. Note that $S_i(G)=S_i(G^*), i=0, 1, 2, 3$, \, $\phi_G(P_2)=\phi_{G^*}(P_2),\phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)=-|N_{G[\Bbb{E}]}(u_i')||N_{G[\Bbb{E}]}(u_i'')|<0$, hence $S_4(G)-S_4(G^*)<0,$ which implies that $G\prec_sG^*$, a contradiction.\vspace{2mm}

If there exists an $i\in \{1,2,\ldots, k\}$ such that $|V_i|=2$. Assume, without loss of generality, that
$V_i=\{u_i, u'\}$, where $u_i$ is adjacent to $u_0\in V_0$. Let
$$
G^*=G-\{u_ix: x\in V_{K_{a_i}}\}+\{yx: y\in V_{K_{a_0}}, x\in V_{K_{a_i}}\setminus\{u_i\}\}.
$$
It is easy to see that $G^*\in\mathscr{G}_n^k\backslash K_n^k$. Note that $S_i(G)=S_i(G^*)$ for $i=0,1$ and $S_2(G)-S_2(G^*)=2(a_i-1)-2(a_i-1)a_0=2(a_i-1)(1-a_0)<0$, hence $S_2(G)<S_2(G^*),$ i.e., $G\prec_s G^*$, a contradiction.

Combining with discussion as above, we obtain that $|V_1|=|V_2|=\cdots=|V_k|=1,$ whence $|V_0|=2$, as desired.
\end{proof}

\vspace{2mm}\noindent {\bf Fact 2}. $a_1=a_2=\cdots=a_k=1$.
\begin{proof}
By a similar discussion as in the proof of Fact 3 in Theorem 2.1, we can get $a_0=n-k$, $a_1=a_2=\dots=a_k=1$. We omit the procedure here.
\end{proof}

\vspace{2mm}\noindent {\bf Fact 3}. $G\cong G_3$, where $G_3=K(n-k,\{1,1,\dots,1\})-u_0u_k+u_0'u_k$, where $u_0u_k$ is a cut edge and $u_0'\in V_{K_{a_0}}\backslash \{u_0\}$.
\begin{proof}
Note that if $G$ has just two cut edges, it is easy to see that $G\cong G_3$ defined as above. Hence in what follows we consider that $G$ contains at least three cut edges.

Let $N_{G[\Bbb{E}]}(u_0)=\{u_1,u_2,\dots,u_m\}$ and $N_{G[\Bbb{E}]}(u_0')=\{u_1',u_2',\dots,u_t'\}$. Without loss of generality, assume that $m\geq t$. Obviously, $t\ge 1$.
At first we show that $t=1$. Otherwise, let
$$
     G^*=G-\{u_0'u_2',u_0'u_3',\dots,u_0'u_t'\}+\{u_0u_2',u_0u_3',\dots,u_0u_t'\}.
$$
It is easy to see that $G^*\in\mathscr{G}_n^k\backslash K_n^k$.
Note that $S_i(G)=S_i(G^*)$ for $ i=0,1,2,3$,\, $\phi_G(P_2)=\phi_{G^*}(P_2),$ and $\phi_G(C_4)=\phi_{G^*}(C_4)$, hence
$$
S_4(G)-S_4(G^*)=4(\phi_G(P_3)-\phi_{G^*}(P_3))=-4m(t-1)<0,
$$
i.e., $G\prec_sG^*$, a contradiction.

Now we are to show that $m=k-1.$ If not, there exists a vertex $u\in \{u_1,u_2,\dots,u_m, u_1',u_2',\dots,u_t'\}$ such that $d_{G[\Bbb{E}]}(u)\ge 2.$ Denote $N_{G[\Bbb{E}]}(u)\setminus\{u_0,v_0\}=\{\hat{u}_1,\hat{u}_2,\dots,\hat{u}_s\}$, $s\geq1$. Let
$$
G^*=G-\{u\hat{u}_1,u\hat{u}_2,\dots,u\hat{u}_s\}+\{u_0\hat{u}_1,u_0\hat{u}_2,\dots,u_0\hat{u}_s\}.
$$
It is easy to see that $G^*\in\mathscr{G}_n^k\backslash K_n^k$.
Notice that $S_i(G)=S_i(G^*)$ for $ i=0,1,2,3$,  $\phi_G(P_2)=\phi_{G^*}(P_2)$ and $\phi_G(C_4)=\phi_{G^*}(C_4)$, hence
$$
S_4(G)-S_4(G^*)=4(\phi_G(P_3)-\phi_{G^*}(P_3))=4s((a_i-1)-(a_0-1)-(m-1))=4s(a_i-a_0)-4s(m-1)<0.
$$
The last inequality follows by $a_i=1< n-k = a_0$ (by fact 2), and $m\ge 1, s\ge 1$. Hence, we get $S_4(G)<S_4(G^*),$ i.e., $G\prec_sG^*$, a contradiction.
so we have $m=k-1, t=1$, which is equivalent to that $G\cong G_3$.
\end{proof}

This completes the proof.
\end{proof}

\section{\normalsize The first and the second graphs in an $S$-order among $\mathscr{G}_n^k$ }\setcounter{equation}{0}
In this section, we are to determine the first and the second graphs in an $S$-order among $\mathscr{G}_n^k$.
Let ${\Bbb E}=\{e_1,e_2,\dots,e_k\}$ be the set of all the cut edges of $G\in\mathscr{G}_n^k$. Note that if we delete an edge, say $e$, from a connected graph $G$, then in the view of $S_2(G)=2|E_G|$, we have $S_2(G)>S_2(G-e)$. In order to determine the first graph in an $S$-order among $\mathscr{G}_n^k$, it suffices to choose the graph such that its size is as small as possible.
\begin{thm}
Of all the connected graphs with $n$ vertices and $k$ cut edges, the first graph in an $S$-order is obtained uniquely at $P_n^k$.
\end{thm}
\begin{proof}
Choose $G\in \mathscr{G}_n^k$ such that it is as small as possible according to the relation $\preceq_s$. If $k=0$, then it is easy to see that $G\cong C_n$ and our result holds immediately. Therefore we may assume that $k\geq1$. We show the following claim at first.
\begin{claim}
$G$ contains exactly one cycle.
\end{claim}
\begin{proof}
Assume to the contrary that $G$ contains at least two cycles. If $G$ contains two cycles $C^1$ and $C^2$ such that $C^1$ and $C^2$ have edges in common; see Fig. 2(a), then let $G^*=G-\{uv, xy\}+ux$ (see Fig. 2(b)); if $G$ contains two cycles $C^1$ and $C^2$ such that $C^1$ and $C^2$ have just one vertex in common; see Fig. 2(c), then let $G^*=G-\{ux, vx\}+uv$ (see Fig. 2(d)). It is routine to check that $G^*\in \mathscr{G}_n^k$
\begin{figure}[h!]
\begin{center}

\psfrag{a}{$C^1$} \psfrag{b}{$C^2$}
\psfrag{t}{$C'$} \psfrag{r}{$C''$}
\psfrag{c}{$u$} \psfrag{d}{$v$}
\psfrag{e}{$x$} \psfrag{f}{$y$}
\psfrag{1}{(a)} \psfrag{2}{(b)}
\psfrag{3}{(c)} \psfrag{4}{(d)}
 \includegraphics[width=120mm]{fig2.eps}\\
  \caption{Graphs used in the proof of Claim 1.
\end{center}
\end{figure}
and in each of the above cases one has $S_i(G)=S_i(G^*),\,i=0,1$ and $S_2(G)-S_2(G^*)=2>0$, hence $ G^*\prec_s G$, a contradiction.

If $G$ contains two cycles $C_l=u_0u_1u_2\dots u_{l-1} $ and $C_j=v_0v_1v_2\dots v_{j-1}$ such that $C_l$ connects $C_j$ by a path $P_i,\, i\ge 2$, whose end vertices are $u_0, v_1$, and the vertex, say $u_t$ (resp. $v_m$), on the cycle  $C_l$ (resp. $C_j$) in $G$ either is of degree 2 or has subgraph $G_t$ (resp. $H_m$) attached, $ 0\leq t \leq {l-1} $, $ 0\leq m \leq {j-1} $; see Fig. 3. Let
$$
  G^*=G-\{u_0u_1,v_1v_2,v_0v_1\}+\{u_0v_2,u_1v_0\} ,
$$
then $G^*\in\mathscr{G}_n^k$. Since $S_i(G)=S_i(G^*),\,i=0,1$. $S_2(G)-S_2(G^*)=2>0$, then $ G^*\prec_s G$, a contradiction. Therefore, $G$ contains exactly one cycle.
\end{proof}
\begin{figure}[h!]
\begin{center}

 \includegraphics[width=150mm]{fig3.eps}\\
  \caption{Graph  $G\Rightarrow G^*$.
\end{center}
\end{figure}

By Claim 1, we know that $G$ is a unicyclic graph. Note that $G$ contains exactly $k$ cut edges, hence $G$ is an $n$-vertex unicyclic graph with girth $n-k$.
By Lemma \ref{lem4} the first graph in an $S$-order among the $n$-vertex unicyclic graph with girth $n-k$ is just the graph $P_n^k,$ as desired.
\end{proof}

At the rest of this section, we are to determine the second graph in an $S$-order among $\mathscr{G}_n^k\, (k \geq 3)$.
\begin{thm}
Of all graphs with $n$ vertices and $k$ cut edges, the second graph in an $S$-order is obtained uniquely at $\hat{U}_n^k\, (k\geq 3)$, where $\hat{U}_n^k$ is obtained by attaching two leafs to the pendant vertex of graph $P_{n-2}^{k-2}$.
\end{thm}
\begin{proof}
Note that if we delete an edge $e$ from a connected graph $G$, then in the view of $S_2(G)=2|E_G|$, we have $S_2(G)>S_2(G-e)$, hence in order to determine the second graph in an $S$-order among $\mathscr{G}_n^k$, it suffices to determine the second graph in an $S$-order among the set of all $n$-vertex unicyclic graphs with girth $n-k$; we denote this set by $\mathscr{U}_n^k$.

Choose $G\in \mathscr{U}_n^k\setminus\{P_n^k\}$ such that it is as small as possible with respect to $\preceq_s$. Note that $\Bbb{E}$ is the set of $k$ cut edges of $G$, hence $G[\Bbb{E}]$ is a forest. We are to show that $G[\Bbb{E}]$ is a tree. If this is not true, then it is equivalent to that there exist at least two vertices, say $u_0, v_0$, on the unique cycle contained in $G$ satisfying $d_G(u_0), d_G(v_0)\ge 3.$

In the edge induced graph $G[\Bbb{E}]$, consider the tree, say $T_1$, containing $u_0$. We are to show that $T_1$ is a path; otherwise, choose a longest path $P=u_0u_1\dots u_p$ in $T_1$ with end-vertex $u_0, u_p$, it is easy to see $d_{T_1}(u_p)=1$.
If there exists $u_i$ with $i\ge 1$ on $P$ such that $d_G(u_i)>2$. Choose a vertex $x$ in $N_G(u_i)\setminus\{u_{i-1}, u_{i+1}\}$ and let
$
G^*=G-u_ix+u_px,
$
then $G^*\in\mathscr{G}_n^k\backslash \{P_n^k\}$.
Note that $S_i(G)=S_i(G^*)$ for $ i=0,1,2,3$,\, $\phi_G(P_2)=\phi_{G^*}(P_2),\phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)\geq1$, hence by
Lemma~1.2(i), we get $S_4(G)-S_4(G^*)>0$, i.e., $G^*\prec_s G$, a contradiction. Hence, we obtain that each vertex $u_i$ on $P$ is of degree 2 in $G$ for  $i=1,2,\ldots, p-1$. Hence, if $d_G(u_0)=3$, then $T_1$ is a path, as desired.
If $d_G(u_0)>3$, then choose $x$ from $N_G(u_0)$ such that $x$ is not on the cycle and the path $P$ contained in $G$. Let
$
G^*=G-u_0x+u_px,
$
then $G^*\in\mathscr{G}_n^k\backslash P_n^k$.
Notice that $S_i(G)=S_i(G^*)$ for $ i=0,1,2,3$, $\phi_G(P_2)=\phi_{G^*}(P_2),\phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)\geq\emph{}2$,  by Lemma 1.2(i), we get $S_4(G)-S_4(G^*)>0,$ i,e., $G^*\prec_s G$, a contradiction.
By a similar discussion as above, we can also show that, in $G[\Bbb{E}]$, the component contains $v_0$ is also a path, say $P'$. For convenience, let $v_0'$ be the neighbor of $v_0$ on $P'$.

   If there exists another vertex $u_0'\neq u_0, v_0$, on the unique cycle contained in $G$ satisfying $d_G(u_0')\ge 3$. Let $G^*=G-\{u_0'x, x\in N_{G[\Bbb{E}]}(u_0')\}+\{u_px, x\in N_{G[\Bbb{E}]}(u_0')\}$,
then $G^*\in\mathscr{G}_n^k\backslash P_n^k$. Note that $S_i(G)=S_i(G^*)$ for $ i=0,1,2,3$, $\phi_G(P_2)=\phi_{G^*}(P_2),\phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)\geq\emph{}1$,  by Lemma 1.2(i), we get $S_4(G)-S_4(G^*)>0,$ i,e., $G^*\prec_s G$, a contradiction. So, we just need to consider there exist two vertices
on the unique cycle contained in $G$ satisfying $d_G(u_0), d_G(v_0)\ge 3.$ Without loss of generality, assume that $|E_P|\geq |E_{P'}|$. Let $G^*=G-v_0v_0'+u_{p-1}v_0'$, it is easy to see that
$G^*\in\mathscr{G}_n^k\setminus\{P_n^k\}$.

\noindent $\bullet$ $k=3$. By Lemma 1.1, we have $S_i(G)\geq S_i(G^*)$ for $i=0,1,\dots,n-2$ and
$S_{n-1}(G)>S_{n-1}(G^*)$. Hence $G^*\prec_sG$, a contradiction.

\noindent $\bullet$ $k\geq4$. Note that $\phi_G(P_2)=\phi_{G^*}(P_2),\phi_G(C_4)=\phi_{G^*}(C_4)$, $\phi_G(P_3)=\phi_{G^*}(P_3),\phi_G(K_{1,3})=\phi_{G^*}(K_{1,3}),\linebreak \phi_G(U_5)=\phi_{G^*}(U_5), \phi_G(B_4)=\phi_{G^*}(B_4)$,
$\phi_G(B_5)=\phi_{G^*}(B_5)$, $\phi_G(C_3)=\phi_{G^*}(C_3)$, $\phi_G(C_6)=\phi_{G^*}(C_6)
$ and $\phi_G(P_4)-\phi_{G^*}(P_4)\geq1$, hence by Lemma 1.2, 1.3, we get that $S_i(G)=S_i(G^*)$ for $i=0,1,2,3,4,5$ and $S_6(G)-S_6(G^*)>0,$ i.e., $G^*\prec_sG$, a contradiction.

Therefore, we obtain that $G[\Bbb{E}]$ is a tree. That is to say, there exists just one vertex, say $u_0$, on the unique cycle such that $d_G(u_0)\ge 3$.
Choose one of the longest paths, say $P:=u_0u_1\dots u_p$, from $G[\Bbb{E}]$. It is easy to see that $u_p$ is a leaf of $G$. Furthermore, we have the following claim.
\begin{claim}
The length of $P$ is $k-1$, i.e., $P:=u_0u_1\dots u_{k-2}u_{k-1}$ and $G[\Bbb{E}]$ is obtained from $P$ by attaching a leaf to $u_{k-2}$ of $P$.
\end{claim}
\begin{proof}
Note that $P=u_0u_1\dots u_p$ is one of the longest paths of $G[\Bbb{E}]$ and $u_p$ is a leaf. Hence, we first show that $d_G(u_0)=3$. Otherwise, choose $x$ from $N_G(u_0)$ such that $x$ is not on the cycle and the path $P$ of $G$. If $d_G(u_i)\geq3$ for some $i\in \{1,2,\dots,p-1\}$, let
$
G^*=G-u_0x+u_px.
$
Obviously, $G^*\in\mathscr{G}_n^k\backslash\{P_n^k\}$.
Note that $S_i(G)=S_i(G^*)$, $ i=0,1,2,3$,\, $\phi_G(P_2)=\phi_{G^*}(P_2),\phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)\geq 2$, hence by Lemma~1.2(i), we get $S_4(G)-S_4(G^*)>0,$ i.e., $G^*\prec_s G$, a contradiction. If $d_G(u_i)=2$ for any $i\in \{1,2,\dots,p-1\}$, let
$
G^*=G-u_0x+u_{p-1}x.
$
Obviously, $G^*\in\mathscr{G}_n^k\backslash\{P_n^k\}$.
Note that $S_i(G)=S_i(G^*)$, $ i=0,1,2,3$,\, $\phi_G(P_2)=\phi_{G^*}(P_2),\phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)\geq 1$, hence by Lemma~1.2(i), we get $S_4(G)-S_4(G^*)>0,$ i.e., $G^*\prec_s G$, a contradiction.

Now we show that $d_G(u_i)=2$, $i=1,2,\dots,p-2$ and $d_G(u_{p-1})=3$.
Note that $G\ncong P_n^k$, hence there exists at least one vertex $u_i\, (1 \leq i\leq {p-1})$ on $P$ such that $d_G(u_i)\geq3$.

If there exists a vertex $u_i\, (1 \leq i\leq {p-1})$ on $P$ such that $d_G(u_i)\geq 4$, then choose $x\in N_G(u_i)\setminus\{u_{i-1}, u_{i+1}\}$ and let
$
G^*=G-u_ix+u_px.
$
Obviously, $G^*\in\mathscr{G}_n^k\backslash P_n^k$. Since $S_i(G)=S_i(G^*)$, $ i=0,1,2,3$. $\phi_G(P_2)=\phi_{G^*}(P_2),\,\phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)\geq2$, by Lemma 1.2(i), we have $S_4(G)-S_4(G^*)>0,$ i.e., $G^*\prec_sG$, a contradiction. Hence,  $\max\{d_G(u_i),i=1,2,\dots,p-1\}=3$.

If $d_G(u_{p-1})=d_G(u_i)=3$ for some $i\in \{1, 2, \ldots, p-2\}$, then choose  $z_1$ in $N_G(u_i)\setminus\{u_{i-1},u_{i+1}\}$ and let
$
G^*=G-u_iz_1+u_pz_1,
$
then $G^*\in\mathscr{G}_n^k\backslash P_n^k$.
Notice that $S_i(G)=S_i(G^*)$, $i=0,1,2,3$. $\phi_G(P_2)=\phi_{G^*}(P_2),\,\phi_G(C_4)=\phi_{G^*}(C_4)$ and $\phi_G(P_3)-\phi_{G^*}(P_3)=1>0$, hence by Lemma 1.2(i), we get that $S_4(G)-S_4(G^*)>0,$ i.e., $G^*\prec_sG$, a contradiction.

If $d_G(u_{p-1})=2,\, d_G(u_i)=3$ for some $i\in \{1, 2, \ldots, p-2\}$, then choose  $z_1$ in $N_G(u_i)\setminus\{u_{i-1},u_{i+1}\}$ and let
$
G^*=G-u_iz_1+u_{p-1}z_1,
$
then it is easy to see that $G^*\in\mathscr{G}_n^k\backslash \{P_n^k\}$.
Note that $S_i(G)=S_i(G^*)$ for $i=0,1,2,3,4,5$, $\phi_G(P_2)=\phi_{G^*}(P_2),\,\phi_G(C_4)=\phi_{G^*}(C_4)$, $\phi_G(P_3)=\phi_{G^*}(P_3),\,\phi_G(K_{1,3})=\phi_{G^*}(K_{1,3}),\,\phi_G(U_5)=\phi_{G^*}(U_5),\, \phi_G(B_4)=\phi_{G^*}(B_4),$ $\phi_G(B_5)=\phi_{G^*}(B_5),\,\phi_G(C_3)=\phi_{G^*}(C_3),\,$
$\phi_G(C_6)=\phi_{G^*}(C_6)$ and $\phi_G(P_4)-\phi_{G^*}(P_4)\geq1$, hence by Lemma 1.2(iii), we get that $S_6(G)-S_6(G^*)>0,$ i.e., $G^*\prec_sG$, a contradiction.

Hence, we obtain that $d_G(u_0)=3, d_G(u_1)=d_G(u_2)=\ldots=d_G(u_{p-2})=2, d_G(u_{p-1})=3$ and $d_G(u_p)=1.$ For convenience, let $N_G(u_{p-1})\setminus\{u_{p-2},u_p\}=\{z_0\}$. It is easy to see that $z_0$ is a leaf; otherwise $G[\Bbb{E}]$ contains a path $P':=u_0u_1\ldots u_{p-1}z_0\ldots z_t$, where $z_t$ is a leaf. It is routine to check that the length of $P'$ is longer than that of $P$, a contradiction. Therefore, $d_G(z_0)=1$, as desired.
\end{proof}
Based on Claim 2, Theorem 3.2 follows immediately.
\end{proof}


\section{Introduction}

Anisotropic flow $v_n$, in particular elliptic flow $v_2$, is one of the
most important observables of ultrarelativistic heavy-ion
collisions~\cite{Ackermann:2000tr,Back:2002gz,Alt:2003ab,Adler:2003kt,Aamodt:2010pa,Chatrchyan:2012wg,ATLAS:2012at,Adamova:2012md}.
It is therefore important to devise the best possible methods to analyze it.
A good measurement should  be reproducible; in particular, it should be done in such a way that one can easily compare results from
different experiments, using different detectors.
For the sake of comparison with theory, an ideal measurement is a well-defined quantity that corresponds to a generic property of the system, closely related to an interesting theoretical concept.
Any such measurement is superior to one that lacks these traits.

In this paper, we argue that the traditional event-plane method~\cite{Poskanzer:1998yz}, which is still used by most of the
major experimental collaborations~\cite{ATLAS:2012at,Adamova:2012md,Adare:2011tg,Chatrchyan:2012ta,Abelev:2012di}
does not satisfy any of the above requirements defining a good measurement.
When the method was first developed, it was assumed that event-by-event fluctuations in $v_n$ were negligible.
However, it is now known that $v_n$ fluctuates significantly within a class of events~\cite{Miller:2003kd,Alver:2006wh,Alver:2010gr}.
As a result, an event-plane measurement of $v_n$ yields an ambiguous measure lying somewhere between
the event-averaged mean value $\langle v_n\rangle$ and the root-mean-square value $\langle v_n^2\rangle^{1/2}$~\cite{Alver:2008zza,Ollitrault:2009ie}.
Where exactly depends on the ``resolution'', which strongly depends on the
experimental setup.
This means that, e.g., the same Pb-Pb collisions at the LHC yield a systematically different value of $v_n$ depending on whether
they are analyzed by ALICE, CMS or ATLAS, and that comparisons to earlier measurements from lower energy collisions at RHIC are ambiguous.
The difference is typically of a few percent for elliptic flow~\cite{Ollitrault:2009ie}, but is larger for higher harmonics like
triangular flow $v_3$~\cite{Alver:2010gr}, which is solely due to fluctuations.

Fortunately, there exist alternative analysis methods that do not suffer from this ambiguity, such as
the two-particle cumulant method~\cite{Borghini:2001vi,Bilandzic:2010jr} or a slight variant of the
traditional event-plane method called the scalar-product method introduced by
the STAR collaboration~\cite{Adler:2002pu}.
These make for a superior measurement because they consistently yield
the rms value of $v_n$, while introducing no disadvantage compared to the traditional event-plane measurements.  Supplemented by higher order cumulant measurements, these make traditional event-plane measurements completely redundant, as they contain no independent information about the underlying flow.

Traditional event-plane analysis methods have also been used to measure higher-order, mixed-harmonic correlations~\cite{Adams:2003zg,Adare:2010ux,Jia:2012sa}.  These measurements also suffer from similar biases as traditional event-plane $v_n$ measurements, but in this case they are much larger~\cite{Gombeaud:2009ye}, causing significant problems even for qualitative comparisons.  Fortunately, these problems can be repaired with a few simple changes.

In Secs.~\ref{s:flowvector} and~\ref{s:subevents},
we recall the principle of the traditional event-plane method and of its variant, the scalar-product method.
In Sec.~\ref{s:flowfluctuations},
we show that the former yields an ambiguous measurement in the presence of flow fluctuations, while the
latter yields an unambiguous result.
These results are already known to experts~\cite{Alver:2008zza}.
For purposes of illustration, we make several simplifications compared to what is typically done in an experiment,
and in Sec.~\ref{s:details} discuss these complications and why they do not change the results.
We also describe in Sec.~\ref{s:combining} a new, systematic way of
improving the accuracy of the scalar-product method
by combining reference flows from ``subevents''.
In Sec.~\ref{s:correlations}, the discussion is extended to the analysis of mixed correlations,
where we show for the first time that the ambiguity resulting from flow fluctuations is much
larger, and the proposed corrected procedure is therefore critical.

\section{Measuring $v_n$}
\label{s:spmethod}

The picture underlying anisotropic flow measurements is that, if the system exhibits strong collective behavior (i.e., ``flow''), particles
in each event are emitted independently according to an underlying one-particle probability distribution~\cite{Luzum:2011mm}
\begin{equation}
\label{prob}
\frac{2\pi}{N}\frac{dN}{d\phi}=1+2\sum_{n=1}^{\infty}v_n \cos n(\phi-\Phi_n),
\end{equation}
where $\phi$ is the azimuthal direction of an emitted particle, $v_n$ is the amplitude of anisotropic flow in the $n$th harmonic, and $\Phi_n$ the corresponding reference angle.  Further assumptions underlying most analyses are that $\Phi_n$ represents a global angle that depends little on pseudorapidity and transverse momentum,  that event-by-event fluctuations of $v_n$ also depend little on pseudorapidity and transverse momentum, and that multiplicity fluctuations within a centrality bin are negligible.

Experiments typically detect anywhere from a few hundred particles to at most a few thousand in a given collision event, while the anisotropy coefficients $v_n$ are typically a few percent or less.  A precise reconstruction of the underlying probability distribution is therefore impossible in a single event.  Information about the underlying probability distribution can only be extracted from (azimuthally symmetric) correlations between outgoing particles, averaged over a large ensemble of events~\cite{Wang:1991qh}.

\subsection{The flow vector}
\label{s:flowvector}

The various experimental estimates of $v_n$ have compact expressions
in terms of the flow vector $\vec Q_n$ in harmonic $n$.
For a given set of $N$ particles belonging to the same event, one defines $\vec Q_n\equiv (|Q_n|\cos(n\Psi_n),|Q_n|\sin(n\Psi_n))$ by~\cite{Poskanzer:1998yz}
\begin{eqnarray}
\label{defqvector}
|Q_n|\cos(n\Psi_n)&=& \frac 1 N \sum_j \cos(n\phi_j)\cr
|Q_n|\sin(n\Psi_n)&=&\frac 1 N \sum_j \sin(n\phi_j),
\end{eqnarray}
where the sum runs through the set of $N$ particles with respective azimuthal angles $\phi_j$.
The flow vector \eqref{defqvector} can also be written in complex form
\begin{equation}
\label{defqcomplex}
Q_n = |Q_n| e^{in\Psi_n}\equiv\frac1 N \sum_j e^{in\phi_j}.
\end{equation}

The original idea behind the event-plane method is that the direction
$\Psi_n$ of the flow vector in a reference detector provides an
estimate of the corresponding
angle $\Phi_n$ in the underlying probability
distribution~\cite{Danielewicz:1985hn}. Because a
finite sample of particles is used, statistical fluctuations cause $\Psi_n$ to differ from $\Phi_n$.
This dispersion is characterized by the ``resolution'', defined as:
\begin{equation}
\label{R0}
  R\equiv\avgev{ e^{in(\Psi_n-\Phi_n)}} =
  \avgev{\Qf{n}{}e^{-in\Phi_n}},
 \end{equation}
where angular brackets denote an average over events.
Note that this average is real by parity symmetry, except for
irrelevant statistical fluctuations.

When the method was developed, it was assumed that dynamical fluctuations
of the underlying probability distribution are negligible, so that
$v_n$ is the same for all events. We then rewrite Eq.~(\ref{R0}) as
\begin{equation}
\label{R}
 R(v_n)\equiv\avgevvn{ e^{in(\Psi_n-\Phi_n)}} = \avgevvn{\Qf{n}{}e^{-in\Phi_n}}.
 \end{equation}
where $\avgevvn{\ldots}$ indicates an average over a large number of events with the same underlying $v_n$,
The dependence of $R$ on $v_n$ can be easily understood if one sees
Eq.~(\ref{defqvector}) as a directed random walk: particles are
emitted randomly, but the underlying probability distribution
(\ref{prob}) is anisotropic.
The resolution $R$ thus depends on the relative magnitude of the anisotropy
$v_n$ to the statistical dispersion $1/\sqrt{N}$.
In the limit $v_n\gg 1/\sqrt{N}$
(infinite number of particles), one can exactly reconstruct
the underlying event
plane so that $\Phi_n = \Psi_n$, and
\begin{equation}
\label{Rhigh}
R(v_n) \xrightarrow[\text{high res.}]{} 1.
\end{equation}
Conversely, when the resolution is low ($v_n\sqrt{N}\ll 1$),
\begin{equation}
\label{Rlow}
R(v_n) \xrightarrow[\text{low res.}]{}
{k v_n},
\end{equation}
where $k$ is independent of $v_n$ and scales as $k\sim\sqrt{N}$.

In the general case, the value is somewhere in between these limits.
Analytic formulas can be obtained for $R(v_n)$ under rather general
assumptions ($N\gg 1$, $v_n\ll 1$, $v_{2n}\ll
1$)~\cite{Ollitrault:1997di}, but they are of little practical use
except when combining subevents.

This nonlinear dependence of the resolution on the underlying flow is
the origin of the difficulties of the event-plane method, which arise
when flow fluctuations are considered.
A simpler quantity
is the projection of the flow vector onto the underlying
direction $\Phi_n$, which directly gives the underlying flow:
\begin{equation}
\label{vn}
\avgevvn{ Q_ne^{-in\Phi_n}} = v_n,
\end{equation}
where we have used Eq.~(\ref{prob}).

\subsection{Correlating subevents}
\label{s:subevents}

Historically, the most common way to access information about the coefficients $v_n$ has been so-called event-plane measurements.
In these analyses,
$v_n$ is extracted from correlations between particles of interest
(e.g., identified particles in a narrow transverse momentum window) and a
different set of particles in a reference detector
(e.g., unidentified particles in a large $p_T$ range), typically
separated by a gap in pseudorapidity~\cite{Adler:2003kt,Alver:2010rt}.

The event-plane method thus correlates the flow vector of particles of
interest, denoted by $Q_{n}$, with the direction of the flow vector
in a reference detector $A$, denoted by $Q_{nA}$.
Assuming that the only correlation between $Q_{n}$ and $Q_{nA}$ is
that resulting from their
correlation with the direction of anisotropic flow $\Phi_n$,
this correlation factorizes:
\begin{eqnarray}
\label{factorization}
\avgevvn{Q_{n}\Qfs{nA}{}}&=&
\avgevvn{Q_{n}e^{-in\Phi_n}}
\avgevvn{\Qf{nA}{}e^{-in\Phi_n}}^*\cr
&=&v_n R(v_{nA}),
\end{eqnarray}
where we have used Eqs.~\eqref{vn} and \eqref{R}, and $v_{nA}$
denotes the value of $v_n$ in the reference detector $A$.
The resolution $R(v_{nA})$ is estimated by correlating $A$ with
additional separate reference detectors;
Each reference detector is called a ``subevent''.
In the simplest
case of two identical subevents ($A$, $B$) located
symmetrically around midrapidity, making use of the factorization
hypothesis:
\begin{eqnarray}
\label{factorization2}
\avgevvn{\Qf{nA}{}\Qfs{nB}{}}&=&
\avgevvn{\Qf{nA}{}e^{-in\Phi_n}}
\avgevvn{\Qf{nB}{}e^{-in\Phi_n}}^*\cr
&=&
\left|\avgevvn{\Qf{nA}{}e^{-in\Phi_n}}\right|^2\cr
&=&R(v_{nA})^2,
\end{eqnarray}
where we have again used Eq.~\eqref{R}.
The event-plane measurement is thus defined as
\begin{equation}
\label{defvnep}
v_n\{EP\}\equiv \frac{\avgev{Q_{n} \Qfs{nA}{}}}{\sqrt{\avgev{\Qf{nA}{}\Qfs{nB}{}}}},
\end{equation}
Since it is impossible to select events according to the underlying probability distribution,
the measurement is taken with averages over all events in a centrality class, denoted by
unadorned angular brackets.
In the absence of flow fluctuations (i.e., if the underlying $v_n$ is
the same in every event),
Eqs.~\eqref{factorization} and~\eqref{factorization2}
ensure that $v_n\{EP\}$ coincides with the underlying $v_n$, up to
experimental errors.

A slight variant of the event-plane method consists in removing the factors of $|Q_n|$ before taking the average in
the numerator and denominator of Eq.~\eqref{defvnep}.
\begin{equation}
\label{defvnsp}
v_n\{SP\}\equiv \frac{\avgev{Q_{n} Q_{nA}^*}}{\sqrt{\avgev{Q_{nA}Q_{nB}^*}}},
\end{equation}
The numerator of Eq.~(\ref{defvnsp}) involves a scalar product of two
vectors $\vec Q_{n}\cdot \vec Q_{nA}$,
and so is referred to as the scalar-product method~\cite{Adler:2002pu}.
In the absence of flow fluctuations, factorization again applies:
\begin{eqnarray}
\label{factorization3}
\avgevvn{Q_{n}Q_{nA}^*}&=&
\avgevvn{Q_{n}e^{-in\Phi_n}}
\avgevvn{Q_{nA}e^{-in\Phi_n}}^*\cr
&=&v_nv_{nA}
\end{eqnarray}
and similarly
\begin{equation}
\label{factorization4}
\avgevvn{Q_{nA}Q_{nB}^*}=v_{nA}^2.
\end{equation}
Therefore $v_n\{SP\}$ also coincides with the underlying $v_n$ in the
absence of flow fluctuations.

\subsection{Flow fluctuations}
\label{s:flowfluctuations}

However, it is now known that $v_n$
fluctuates significantly from event to event~\cite{Alver:2006wh}.
To make it clear what is really measured in this case,
we evaluate event averages in two steps, by first
averaging over events with the same $v_n$, then combining
bins of $v_n$.
\begin{equation}
\label{twosteps}
\avgev{\ldots} \equiv \avgvn{\avgevvn{\ldots}}.
\end{equation}
We apply this decomposition to Eq.~\eqref{defvnep} and evaluate the
inner average using Eqs.~\eqref{factorization} and
\eqref{factorization2}:
\begin{equation}
v_n\{EP\}
= \frac{\avgvn{v_n R(v_{nA})}}{\sqrt{\avgvn{R(v_{nA})^2}}},
\end{equation}
Note that $\langle R(v_{nA})^2\rangle\not=\langle R(v_{nA})\rangle^2$,
so that the resolution correction
is no longer  a simple projection of the measured event plane $\Psi_n$
onto the ``true'' event plane $\Phi_n$.

In the limit of perfect resolution (i.e., the number of particles used in the reference detector goes to infinity), $R(v_{nA})\simeq 1$ and $v_n\{EP\}$ does indeed measure the event-averaged mean $v_n$ from Eq.~\eqref{prob},
\begin{equation}
\label{vnhigh}
v_n\{EP\} \xrightarrow[\text{high res.}]{} \avgev{ v_n} .
\end{equation}
In reality, the resolution is not perfect, and the result is usually closer to the low resolution limit~\cite{Alver:2008zza}.
In this limit,
$R(v_{nA})\propto v_{nA}$.
Assuming that flow fluctuations are global, i.e., $v_n/v_{nA}$ does not fluctuate significantly,
the event-plane measurement thus yields a root-mean-square value,
\begin{equation}
\label{vnlow}
v_n\{EP\} \xrightarrow[\text{low res.}]{}
\sqrt{\avgev{ v_n^2 }} .
\end{equation}
\begin{figure}
\includegraphics[width=\linewidth]{ratios}
\caption{(Color online) Ratio of the rms $v_n$, corresponding to the low-resolution limit of Eq.~(\ref{defvnep}) integrated over $p_T$, to the mean $v_n$, corresponding to the high-resolution limit, as a function of the number of participant nucleons (binned in 5\% centrality intervals), for a Pb-Pb collision at 2.76 TeV per nucleon pair. We model flow fluctuations by assuming $v_n\propto\varepsilon_n$ in each event, where $\varepsilon_n$ is the anisotropy of the initial distribution in the corresponding harmonic, defined as in Ref.~\cite{Gardim:2011xv}. The value of  $\varepsilon_n$ in each event is obtained from the Phobos Monte Carlo Glauber model~\cite{Alver:2008aq}. For $v_3$, the ratio is close to $2/\sqrt{\pi}\simeq 1.13$, corresponding to Gaussian fluctuations~\cite{Voloshin:2007pc}. }
\label{fig:ratios}
\end{figure}
In general, the event-plane method yields a result which may lie
anywhere between the two limits \eqref{vnhigh} and \eqref{vnlow}. The
exact measured quantity depends the detector acceptance---even after
the resolution correction is applied---so that the measurement is ambiguous.

The difference between the two limits
ranges from 6 to 13\%, as illustrated in Fig.~\ref{fig:ratios}.  As the field enters an era of precision physics,  comparisons of different experimental analyses~\cite{Ollitrault:2009ie} and of theory to experiment~\cite{Gardim:2012yp} are significantly complicated by this dependence on
analysis details.  For example, the large detector acceptance and high multiplicities of recent measurements at the LHC allow for a larger resolution than was available at RHIC.  The natural choice (and what has been done) is to take advantage of this extra resolution to minimize the statistical uncertainty of the measurement.  The penalty, however, is that comparisons to earlier measurements become ambiguous, and one has difficulty determining from these measurements how much the flow changes, e.g., with collision energy.

Theoretical comparisons are hampered for the same reason.  Theorists have access to more information than experiments --- their `detectors' have perfect efficiency and suffer no dead spots or holes in coverage; i.e., they can see all particles that are produced.  However, if they succumb to the temptation to make use of this extra information to improve statistics (or they simply lack detailed information about detector performance to appropriately degrade the data) comparisons to measurements can become ambiguous and unreliable --- even if they otherwise follow the exact same procedures as the experiment~\cite{Holopainen:2010gz,Petersen:2011sb,Pang:2012he}.

Fortunately, this ambiguity can be removed by using the scalar-product  method.
Although it was originally introduced for unrelated reasons, it gives a well-defined measurement in the presence of flow fluctuations~\cite{Ollitrault:2009ie},
despite differing only trivially from the traditional analysis.
When $v_n$ fluctuates, we again apply the decomposition
\eqref{twosteps} to Eq.~\eqref{defvnsp} and evaluate the numerator and
the denominator using Eqs.~\eqref{factorization3} and \eqref{factorization4}:
\begin{equation}
v_n\{SP\}
= \frac{\avgvn{v_n v_{nA}}}{\sqrt{\avgvn{v_{nA}^2}}}
=\sqrt{\avgev{v_n^2}},
\end{equation}
where we have again used the hypothesis that $v_n/v_{nA}$ does not
fluctuate significantly.
Therefore, the scalar-product method always yields the root-mean-square $v_n$, regardless of the details of the analysis, and makes for a superior measurement.

One can also choose to measure a two-particle correlation~\cite{Aamodt:2011by},
which is essentially equivalent to a scalar-product analysis, and also always measures
this same unambiguous root-mean-square value~\cite{Miller:2003kd}.  It is important to
emphasize, however, that even when an event-plane-type analysis is preferred for practical
reasons, only a trivial change to the standard analysis is required in order to obtain a
well-defined observable.

If the resolution is large enough, higher-order cumulants~\cite{Borghini:2001vi,Bilandzic:2010jr} can be analyzed.  These then yield an unambiguous measurement of higher-order, even moments of the distribution of $v_n$, i.e. $\langle (v_n)^{2k}\rangle$~\cite{Miller:2003kd}.
Since a standard event-plane method measures a quantity that is different from any of these
individual observables, one might naively think it useful to perform both analyses in order to
obtain the maximum amount of independent information.  However,
it has been proven~\cite{Ollitrault:2009ie} that the event-plane method, in addition to being ambiguous, contains no independent information beyond that contained in the first two cumulants,  $v_n\{2\}$ and $v_n\{4\}$ (regardless of whether nonflow correlations are present in the system).  So there is no reason to use a standard event-plane method in any future analysis.

\subsection{Practical details}
\label{s:details}

Actual measurements often differ slightly from the above idealized discussion.   The flow vector~\eqref{defqcomplex} is typically defined~\cite{Poskanzer:1998yz} without the normalization factor $N$.  Similarly, the numerators in Eqs.~\eqref{defvnep} and~\eqref{defvnsp} are calculated as a sum over the particles of interest in all events, before normalizing by the total number of particles after the sum over events.  Thus, there are weighting factors of $N$ and $dN/dp_T$, respectively, inside the event averages, which become important only if large enough centrality bins are used such that multiplicity and spectrum fluctuations are significant.

Second, the flow vector used to estimate the event plane is often calculated as a weighted average of particles.
In particular, if it is measured using a calorimeter, the particles are weighted according to their energy, while
a $p_T$-dependent weight is often used to increase the resolution or to remove non-flow
correlations~\cite{Luzum:2010fb}.  In this case $v_{nA}$ above refers
to a weighted average.

Third, in the case where identical subevents are not available, the
analysis can be done with three arbitrary subevents $A$, $B$, and
$C$~\cite{Poskanzer:1998yz}. One then does the following replacement
\begin{equation}
\avgev{Q_{nA}Q_{nB}^*}\rightarrow\frac{\avgev{Q_{nA}Q_{nB}^*}\avgev{Q_{nA}Q_{nC}^*}}{\avgev{Q_{nB}Q_{nC}^*}}
\end{equation}
in the denominator of Eq.~\eqref{defvnsp}, and a similar modification
in the resolution correction of Eq.~\eqref{defvnep}.

Fourth, we have used a complex notation throughout this
section. However, all quantities are real after averaging over events,
except for irrelevant experimental errors. Therefore $\avgev{\ldots}$
should be replaced by $\Re\avgev{\ldots}$ everywhere.

Finally, if any of the flow vectors in the numerator of Eqs.~\eqref{defvnep} and~\eqref{defvnsp}
are calculated from the same or overlapping sets of particles, care must be made to remove self-correlations~\cite{Danielewicz:1985hn}.

\subsection{Combining subevents}
\label{s:combining}

We end this section with a brief description of how the precision of the scalar-product method can be improved beyond previous implementations.
Since at least two reference detectors $A$ and $B$ are needed in order
to carry out the flow analysis, it is tempting to combine the information from both detectors into a single measurement with reduced statistical uncertainty. In the standard event-plane method, this can be done for identical
subevents at the expense of additional hypotheses and algebraic complications \cite{Poskanzer:1998yz,Ollitrault:1997di},
but there is no known way of recombining non-identical subevents, as in the three-subevent method.

With the scalar-product method, combining measurements from two reference detectors $A$ and $B$ is straightforward, even if they are not identical.
One simply measures $v_n$ independently with respect to $A$ and to $B$.
By linearity of the scalar product, combining both measurements (denoted by $v_{n}\{SP,A\}$ and $v_n\{SP,B\}$) amounts to taking
a weighted average. We show in Appendix \ref{s:appendix} that the optimal weighting is
\begin{equation}
\label{optweight}
v_n\{SP\}\equiv\frac{\chi_A^2 v_{n}\{SP,A\}+\chi_B^2 v_n\{SP,B\}}{\chi_A^2 +\chi_B^2 },
\end{equation}
where $\chi_A$ is the dimensionless resolution parameter.
For identical subevents, $v_n$ is the mean of $v_{n}\{SP,A\}$ and
$v_n\{SP,B\}$ by symmetry:
\begin{equation}
v_n\{SP\}=\frac{v_{n}\{SP,A\}+v_n\{SP,B\}}{2}.
\end{equation}
For non-identical subevents, a third subevent $C$ is
required in order to determine the resolution parameter: $\chi_A$ is
given by
\begin{equation}
\label{defchiA}
\frac{1}{\chi_A^2}+1\equiv
\frac{\langle (\vec Q_{nA})^2\rangle\langle\vec Q_{nB}\cdot\vec
  Q_{nC}\rangle}
{\langle\vec Q_{nA}\cdot\vec
  Q_{nB}\rangle\langle\vec Q_{nA}\cdot\vec Q_{nC}\rangle},
\end{equation}
and $\chi_B$ is given obtained through the substitution
$A\leftrightarrow B$ in Eq.~\eqref{defchiA}.
Note that when detectors are combined, their resolution parameters
$\chi$ add in quadrature.
Generalization of Eq.~\eqref{optweight} to three subevents $A$, $B$
and $C$ is straightforward.

\section{Higher-order correlations}
\label{s:correlations}

Fourier harmonics of the azimuthal distribution are now measured up to $v_4$~\cite{Adare:2011tg}
at RHIC and up to $v_5$~\cite{ALICE:2011ab,Chatrchyan:2012wg} and
$v_6$~\cite{ATLAS:2012at} at LHC.
Much additional information is contained in mixed correlations between different
harmonics~\cite{Teaney:2010vd,Bhalerao:2011yg,Bhalerao:2011bp,Teaney:2012ke},
which give information about event plane angles $\Phi_n$ and will likely play a large part in upcoming measurements.
Before rushing into analysis, it is important to define observables for good measurements,
which will allow unambiguous comparison between different experiments, and with theory.

The ATLAS collaboration has recently released preliminary measurements of an extensive set of correlations between
event planes using traditional methods~\cite{Jia:2012sa}. For illustration, we consider the first of these correlations.  It is a correlation between the event planes $\Psi_4$ and
$\Psi_2$, namely, $\langle\cos 4(\Psi_4-\Psi_2)\rangle$,  which is then divided by a resolution factor in order to unravel the correlation between the underlying reference directions $\Phi_4$ and $\Phi_2$.
They thus write:
\begin{equation}
\label{atlascorrection}
\langle\cos 4(\Phi_4-\Phi_2)\rangle=\frac{\langle\cos 4(\Psi_4-\Psi_2)\rangle}
{\langle\cos 4(\Psi_4-\Phi_4)\rangle\langle\cos 4(\Psi_2-\Phi_2)\rangle}.
\end{equation}
This equation is based on the same hypotheses as the event-plane method, which fail if $v_2$ and $v_4$ fluctuate. Specifically, the numerator of the right-hand side does not factorize into
$\langle\cos 4(\Psi_4-\Phi_4)\rangle\langle\cos 4(\Psi_2-\Phi_2)\rangle\langle\cos 4(\Phi_4-\Phi_2)\rangle$,
and the resolution corrections estimated using standard procedures  do not actually correspond to
$\langle\cos 4(\Psi_4-\Phi_4)\rangle$ and $\langle\cos 4(\Psi_2-\Phi_2)\rangle$.

Using the notations introduced in the previous section, and assuming
symmetric subevents $A$ and $B$ for simplicity, the observable
actually measured is
\begin{equation}
\label{atlas42}
\avgev{\cos 4 (\Phi_4 - \Phi_2)}\{EP\}
\equiv \frac
{\avgev{\Qf{4A}{}
\Qfs{2B}{2}}}
{\sqrt{\avgev{\Qf{4A}{}\Qfs{4B}{}}}\sqrt{\avgev{
\Qf{2B}{2}\Qfs{2A}{2}
}}}.
\end{equation}
In the presence of flow fluctuations, the average over events can be
evaluated in two steps following \eqref{twosteps}.
In addition to $R_n$ given by Eq.~(\ref{R}), we
define a similar quantity $\mathcal{R}_n$
\begin{equation}
\label{R2}
\mathcal{R}_n\equiv \sqrt{\avgevvn{ e^{2in(\Psi_n-\Phi_n)}}} = \sqrt{\avgevvn{\left(\Qf
{n}{}e^{-in\Phi_n}\right)^2}}
 \end{equation}
 which has the same limits, Eqs.~\eqref{Rhigh} and \eqref{Rlow},  but can differ at an arbitrary resolution.
With this notation,
\begin{equation}
\avgev{\cos 4 (\Phi_4 - \Phi_2)}\{EP\}
= \frac
{\avgvn{
R_4 \mathcal{R}_2^2 e^{ 4i (\Phi_4 - \Phi_2)}
}}
{
\sqrt{\avgvn{R_4^2}}
\sqrt{\avgvn{\mathcal{R}_2^4}}
}
\end{equation}

In the limit where the resolutions on both harmonics are perfect, the quantity measured by ATLAS is indeed the nominal value, corresponding to the left-hand side of Eq.~\eqref{atlascorrection}:
\begin{equation}
\label{mixedhigh}
\cos 4(\Psi_4-\Psi_2)\{EP\}\xrightarrow[\text{high res.}]{}  \langle\cos 4(\Phi_4-\Phi_2)\rangle.
\end{equation}
In the limit of low resolution, however, repeating the same reasoning as in the previous section,
what is actually measured is the quantity
\begin{equation}
\label{mixedlow}
\cos 4(\Psi_4-\Psi_2)\{EP\}\xrightarrow[\text{low res.}]{}
\frac{\langle v_{4A}v_{2A}^2\cos
  4(\Phi_4-\Phi_2)\rangle}{\sqrt{\langle v_{4A}^2\rangle\langle v_{2A}^4\rangle}}.
\end{equation}
As before, the measured value is generally between the two limits.\footnote{Note that the low-resolution limit \eqref{mixedlow} lies between $-1$ and $+1$ by construction, even though it does not reduce to a simple angular correlation.}
Similar expressions can be written for the other correlations in the large set measured by ATLAS.
Unlike measurements of $v_n\{EP\}$, however, there is no known way to even estimate
where between these limits the result lies based only on the reported event-plane resolution.

Note that the same ambiguity plagues previous measurements of the similar ($p_T$-differential) quantity, $v_4$ with respect to the event-plane of
elliptic flow $\Psi_2$~\cite{Adams:2003zg,Adare:2010ux}.
Not only does the result depend on the resolution, it also depends on how the resolution correction is defined, as the seminal paper \cite{Poskanzer:1998yz} proposes two possible implementations, which turn out to be different in the presence of flow fluctuations.

The high resolution limit of these measurements is the nominal quantity
\begin{equation}
\label{v4high}
v_4\{\Psi_2\}\xrightarrow[\text{high res.}]{}  \langle v_4\cos 4(\Phi_4-\Phi_2)\rangle.
\end{equation}
The low-resolution limit depends on the actual implementation of the resolution correction. STAR~\cite{Adams:2003zg} uses Eq.~(11) of \cite{Poskanzer:1998yz}, which reduces to
\begin{equation}
\label{v4lowSTAR}
v_4\{\Psi_2\}\xrightarrow[\text{low res.}]{}  \frac{\langle v_4
  v_{2A}^2\cos 4(\Phi_4-\Phi_2)\rangle}{\langle v_{2A}^2\rangle}
\end{equation}
in the low-resolution limit, where again $v_{2A}$ is integrated over the reference detector.
PHENIX uses the same implementation as ATLAS (Eq.~(14) or Eq.~(16) of \cite{Poskanzer:1998yz}) which yields, in the low-resolution limit,
\begin{equation}
\label{v4lowPHENIX}
v_4\{\Psi_2\}\xrightarrow[\text{low res.}]{} \frac{\langle v_4 v_{2A}^2\cos 4(\Phi_4-\Phi_2)\rangle}{\sqrt{\langle  v_{2A}^4\rangle}}.
\end{equation}

As recently
demonstrated in Ref.~\cite{Gardim:2012yp} in full
event-by-event hydrodynamic calculations, this ambiguity of the event-plane method is a significant source of uncertainty when comparing experiment to theory.
In fact, it should already have been apparent that the effect of
detector resolution in measurements such as these is much larger than
for the $v_n\{EP\}$ measurements described above.
The difference between Eqs.~(\ref{v4lowSTAR}) and (\ref{v4lowPHENIX})
likely explains why the values of $v_4\{\Psi_2\}$ are systematically
higher for STAR than for PHENIX by some 10\%~\cite{Gombeaud:2009ye}.
In Ref.~\cite{Adams:2003zg} the STAR collaboration measured
$v_4\{\Psi_2\}$, but in addition measured a 3-particle correlation
$v_4\{3\}$, which corresponds to the low-resolution limit of their event-plane measurement.
The STAR collaboration
finds that $v_4\{3\}$ is larger than $v_4\{\Psi_2\}$ by 20\% for mid
central collisions. This difference is much larger than the difference
between, e.g., $v_2\{EP\}$ and the low resolution limit $v_2\{SP\}$ in
the same experiment (which is roughly 5\%).

In order to illustrate the possible full dependence on resolution, we use here a simplified calculation, though the results are consistent with more sophisticated calculations~\cite{Gardim:2012yp}.  It is known from event-by-event hydrodynamic calculations that $p_T$-integrated $v_2$, $v_4$, and the corresponding reference directions $\Phi_2$ and $\Phi_4$ can be accurately predicted in each event from the initial eccentricities according to~\cite{Gardim:2011xv}
\begin{eqnarray}
v_2 e^{2i\Phi_2}&=&a\varepsilon_2 e^{2i\Phi_{in,2}}\cr
v_4 e^{4i\Phi_4}&=&b\varepsilon_4 e^{4i\Phi_{in,4}}+c(\varepsilon_2 e^{2i\Phi_{in,2}})^2,
\end{eqnarray}
where $a$, $b$, $c$ are real coefficients, and $\varepsilon_n$ and $\Phi_{in, n}$ are the initial anisotropy in harmonic $n$ and its reference direction, as defined in Ref.~\cite{Gardim:2011xv}.

\begin{figure}
\includegraphics[width=\linewidth]{corr42}
\caption{(Color online)
Top, left: low and high resolution limits of the correlation between $\Phi_2$ and $\Phi_4$, defined by Eqs.~\eqref{mixedlow} and \eqref{mixedhigh}, versus number of participants.
Top, right: low and high resolution limits for integrated $v_4\{\Psi_2\}$, defined  by Eqs.~\eqref{v4lowSTAR},  \eqref{v4lowPHENIX} and \eqref{v4high}. Bottom panels: ratios of the low-resolution to high-resolution results. The nominally-measured values correspond to the high-resolution limit, which can differ from what is actually measured (usually closer to the low-resolution limit) by up to a factor 2.}
\label{fig:mixed}
\end{figure}

We thus compute $\varepsilon_n$ and $\Phi_{in,n}$ using the PHOBOS Monte Carlo Glauber~\cite{Alver:2008aq} and take the values of $b$ and $c$ from the viscous hydrodynamic calculation by Teaney and Yan~\cite{Teaney:2012ke}, for simplicity taking centrality-independent values of $b=0.018$ and $c = 0.07$~\footnote{Note that Teaney and Yan use cumulants of the initial distribution, which are linear combinations of our moments: with their notation, $b=w_4/{\cal C}_4$ and $c=w_{4(22)}/\varepsilon_2^2+3(w_4/{\cal C}_4)\langle r^2\rangle^2/\langle r^4\rangle$. We take $w_4/{\cal C}_4\simeq 0.018$ and  $w_{4(22)}/\varepsilon_2^2\simeq 0.04$ from their Fig.~2, right, and we estimate $\langle r^2\rangle^2/\langle r^4\rangle\simeq 0.6$ from a Glauber calculation.}.

The right-hand side of Eqs.~\eqref{mixedhigh} and \eqref{mixedlow} are displayed in
Fig.~\ref{fig:mixed} (top, left), as well with their ratio (bottom, left), and similarly for Eqs.~\eqref{v4high},  \eqref{v4lowSTAR} and~\eqref{v4lowPHENIX} on the right side of the figure.  The ratio varies from 1.4 to more than 2 (in agreement with full event-by-event hydrodynamic calculations of $v_4\{\Psi_2\}$~\cite{Gardim:2012yp}).
Comparing with Fig.~\ref{fig:ratios}, one sees that the ambiguity induced by the event-plane method is much worse for mixed correlations that for individual measurements of $v_n$.

As a recent illustration of the problems that can arise from this, we point to the correlations calculated in Ref.~\cite{Qiu:2012uy}, corresponding to the high resolution limit of the recent preliminary ATLAS measurements --- i.e., the quantities that were nominally claimed as measured.  They are all clearly smaller in magnitude than the measurements, despite each observable having the correct sign and centrality dependence.  Naively, this seems to indicate that the theory needs to be changed somehow to accommodate this difference, but in fact the finite resolution of the experiment could in principle explain the entire discrepancy.  Further, while it is straightforward to calculate either the low or the high resolution limit, as done in that work, a calculation that reliably corresponds exactly to the measured quantity adds considerable difficulty. In fact, it is not possible without access to more information about the experimental details than is available.

Fortunately, the ambiguity of the event-plane method can easily be removed by using a straightforward generalization of the scalar-product method.
The right-hand side of Eq.~\eqref{mixedlow} is given by
\begin{equation}
\label{mixedsp}
\frac{\langle v_{4A}v_{2A}^2\cos 4(\Phi_4-\Phi_2)\rangle}{\langle
  v_{2A}^2\rangle\sqrt{\langle v_{4A}^2\rangle}}=
\frac
{\avgev{Q_{4A}Q_{2B}^{*2}}}
{\sqrt{\avgev{Q_{4A}Q^*_{4B}}}\sqrt{\avgev{
Q_{2B}^2Q_{2A}^{*2}
}}},
\end{equation}
which we suggest as a replacement for Eq.~(\ref{atlas42}).
In the same way as for individual measurements of $v_n$, this method
yields a result which is unambiguous and independent of the number of particles selected for analysis.
Note that the numerator is a sum over all triplets of particles of $\langle\cos(2\phi_1+2\phi_2-4\phi_3)\rangle$. The quantity in Eq.~\eqref{mixedsp} is thus identical to the type of scaled correlations introduced in~\cite{Bhalerao:2011yg}.

Generalization of the above discussion to $v_4\{\Psi_2\}$ and other mixed correlations~\cite{Jia:2012sa,Bhalerao:2011yg} is straightforward. In general, higher-order correlations involve higher moments of the distribution of anisotropic flow, and have therefore an increased sensitivity to flow fluctuations.

Note that the particular correlation between $\Phi_2$ and $\Phi_4$ studied above can be contaminated by nonflow correlations; Therefore it is important that the flow vectors $Q_2$ and $Q_4$ are determined in regions separated by a pseudorapidity gap~\cite{Jia:2012sa}. Other mixed correlations, such as the correlation between $\Phi_2$ and $\Phi_3$, are not sensitive to nonflow correlations. The need for gaps in pseudorapidity must be considered on a case-by-case basis~\cite{Bhalerao:2011ry}.

\section{Conclusion}
We have explained that measurements of anisotropic flow using the event-plane method are ambiguous because the result depends on analysis details. This dependence, which is due to event-by-event flow fluctuations, is typically up to a few percent for $v_2$ and 10\% for $v_3$ and higher harmonics.
For mixed correlations involving event planes from different harmonics, the dependence is much larger --- we have demonstrated that the result may vary by a factor 2 depending on analysis details. We have shown that these ambiguities of the event-plane method can be repaired with only minor modifications and without any additional complication or drawbacks. We therefore conclude that the traditional event-plane method should be abandoned in future analyses.

\begin{acknowledgments}
ML is supported by the European Research Council under the Advanced Investigator Grant ERC-AD-267258.
We thank Instituto de Fisica, Sao Paulo, where this paper was written,
for hospitality, and FAPESP-CNRS for financial support (project 2011/51864-0)

\end{acknowledgments}