%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Structure of Inifnite Locally-Finite 2-connected Graphs
%
%  by Carl Droms, Brigitte Servatius and Herman Servatius
%
%  LaTeX source for a 10 page article.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[12pt,bezier]{article}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 2
            (1995), \#R17 \hfill}
\thispagestyle{empty}

\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{-.35in}
\addtolength{\textwidth}{1.2in}
\addtolength{\textheight}{1.5in}


\hyphenation{u-nique con-nect-ed}
\newcommand{\A}{\alpha}    % initial vertex symbol
\renewcommand{\O}{\omega}    % terminal vertex symbol
\newcommand{\ignore}[1]{}        
\newcommand{\later}[1]{}        
\newcommand{\bridge}{bridge}     
\newcommand{\bridges}{bridges}   
\newcommand{\branch}{branch}
\newcommand{\branches}{branches}
\newcommand{\amalgam}{+}
\newcommand{\contract}{\cdot}
\newcommand{\Tree}{{\cal T}}
\newcommand{\union}{\cup}
\newcommand{\intersect}{\cap}
\newenvironment{defn}{\begin{trivlist} 
        \item[\hspace{\parindent}{\sc Definition:}]}{\end{trivlist}}

\newcommand{\present}[2]{\langle #1 \mid #2 \rangle}
\newcommand{\grp}[1]{\langle #1 \rangle}
\newcommand{\join}[1]{\mathbin{\amalgam_{#1}}}
\newcommand{\Bar}[1]{\overline{#1}}
\newcommand{\similar}{\cong}  %H: Just one twiddle?
\newcommand{\iso}{\cong}
\newcommand{\closerthan}{\preceq}
\newcommand{\inv}{^{-1}}
\newcommand{\directprod}{\times}
\newcommand{\freeprod}{\ast}
\newcommand{\supp}[1]{\mbox{{\rm supp(}$#1${\rm )}}}
\newcommand{\link}[1]{\mbox{{\rm link(}$#1${\rm )}}}
\newcommand{\starr}[1]{\mbox{{\rm star(}$#1${\rm )}}}
\newcommand{\FreeProduct}[2]{\rm {\raisebox{-2.9ex}
                 {\shortstack{ $_{#1}$ \\
                               {\huge *} \\
                               \raisebox{0ex}[.5ex]{$^{#2}$} }}}}
\newcommand{\vol}[1]{{\bf #1}}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newenvironment{proof}{\noindent {\bf \sc Proof:}}{$\Box$}


\begin{document}

\begin{center}
{\Large\bf The Structure of Locally Finite Two-Connected Graphs}\\[5mm]
{\bf Carl Droms\footnote{Supported by a James Madison 
                         University Faculty
                          Summer Research grant.}, 
     Brigitte Servatius} and 
{\bf Herman Servatius}\\[8mm]
Submitted: May 15, 1995; Accepted: September 4, 1995.\\[12mm]
\end{center}

         
\date{{\normalsize Submitted: May 15, 1995; Accepted: September 4, 1995.}}

\begin{abstract}
     We expand on Tutte's theory of $3$-blocks for 
     $2$-connected graphs, generalizing it to apply to infinite,
     locally finite graphs, and giving necessary and sufficient 
     conditions for a labeled tree to be the $3$-block tree of a 
     $2$-connected graph. 
\end{abstract}

\medskip

\noindent {\small\em Mathematics Subject Classification:} 05C40, 05C38, and 05C05.

\noindent {\small\em Key Words and Phrases:} 
       Tutte connectivity, $3$-block, $3$-block tree
       
\medskip


\section{Introduction}
Connectivity properties
of graphs
are among the basic aspects of graph theory. 
Every graph is the disjoint union of its connected components,
and every connected graph is 
the edge disjoint union of its maximal $2$-connected subgraphs,
encoded in the block-cutpoint tree.  
A canonical decomposition for finite $2$-connected graphs was given by
Tutte~\cite{Tutte1} in the form of the $3$-block tree,
and generalized to matroids by 
Cunningham and Edmonds~\cite{CunninghamEdmonds}.  
Such decompositions are important tools in inductive arguments and 
constructions. 
Hopcroft and Tarjan~\cite{HopcroftTarjan} gave an important 
algorithm for computing
the $3$-block tree of a graph in $O(V + E)$ time, 
which is comparable to the 
complexity of computing other non-canonical decompositions, say the ear
decomposition, and is also applicable to matroids. 
Effective decompositon schemes for graphs of connectivity $3$ and higher
have been given, but none are canonical, and 
in Section~\ref{HigherSect} we argue that none will be forthcoming. 
The uniqueness of Tutte's construction may be exploited to study the
symmetry properties of graphs with low connectivity, 
\cite{SS95} and~\cite{DSS95a}, particularly in the case of planar 
graphs~\cite{DSS95b}.
In this paper we will examine the interpretation of 
Tutte's decomposition and extend the theory to infinite graphs.

\section{$n$-Connectivity}
We are concerned with the structure of locally finite graphs of 
connectivity less than $4$, allowing graphs to have loops and 
multiple edges.
If a graph $G$ has at least $3$ vertices and is not 
a triangle, then $G$ is defined to be {\em $n$-connected} 
if $G$ has girth 
at least $n$ and 
any two vertices of $G$ are joined by $n$ internally disjoint paths.  
To avoid uninteresting special cases, 
the connectivities of the small graphs in Figure~\ref{DumbyFig} are 
said to be infinite.  
\begin{figure}[htb]
	\centering  
    \setlength{\unitlength}{0.50pt}
    \begin{picture}(491,121)
    \thinlines
    \put(428,86){\circle*{10}}
              \put(455,45){\circle*{12}}
              \put(397,45){\circle*{10}}
              \put(428,87){\line(-3,-4){31}}
              \put(455,44){\line(-2,3){27}}
              \put(396,44){\line(1,0){59}}
              \put(303,44){\line(1,0){69}}
              \put(303,42){\line(-1,-1){1}}
              \put(278,45){\circle*{8}}
              \put(244,43){\oval(70,26)}
              \put(209,44){\circle*{10}}
              \put(372,45){\circle*{10}}
              \put(338,44){\oval(70,26)}
              \put(304,43){\circle*{8}}
              \put(177,44){\circle*{2}}
              \put(175,42){\circle*{8}}
              \put(135,42){\circle*{8}}
              \put(136,42){\line(1,0){38}}
              \put(35,42){\circle*{2}}
              \put(36,43){\circle*{12}}
              \put(90,40){\circle*{2}}
              \put(84,42){\circle*{10}}
              \put(85,61){\circle{40}}
    \end{picture}
	\caption{Infinitely connected graphs.\label{DumbyFig}}
	\protect
\end{figure}
This definition of $n$-connectivity, 
also known as {\em Tutte connectivity,} 
was introduced in~\cite{Tutte2}, 
see also~\cite{Oxley}, and differs for simple graphs from the usual 
definition of $n$-connectivity only for $n > 3$, with the exception of the 
special cases in Figure~\ref{DumbyFig}, and has the advantage of being 
generalizable to matroids,~\cite{Tutte3}, 
and being invariant under dualization.


We call a graph on two vertices connected by parallel edges a {\em 
multilink}. Note, that with the above definition, multilinks on more than 
three edges are only 2--connected. 



      For any graph $G$ , there is an equivalence
relation defined on the edges of $G$ by setting $e \similar e'$ if 
$e$ and $e'$ lie on a common cycle, or $e=e'$.  The 
equivalence classes are either single edges or
induce maximal $2$-connected subgraphs of 
$G$, and are called the {\em blocks} (or {\em $2$-blocks}) 
of $G$.  The {\em block--cutpoint tree} is the graph defined 
on the union of the set of blocks and 
the set of cutpoints, with a cutpoint adjacent to each of the 
blocks to which it belongs.  
It is obvious that this graph is a tree.  
In general, one might hope that any $k$--connected graph 
decomposes as the union of subgraphs which are either 
$k+1$--connected or have at most $k$ vertices.  However, this
is not the case, since a  $2$-connected graph
may have no non-trivial $3$-connected subgraphs at all, 
as in 
Figure~\ref{AmalgFig}.

In the interest of analogy, therefore,
it is preferable to regard a block--cutpoint tree as an 
encoding of the instructions for assembling a $1$-separable graph 
from simpler pieces using the operation of vertex--union.  

Let $A$ and $B$ be graphs and suppose there are functions
$f_A:e \rightarrow A$ and 
$f_B:e \rightarrow B$, where $e$ is a graph consisting of 
two vertices $1$ and $2$ joined by an edge which we will also 
call $e$.
\begin{figure}[htb]
\centering
\unitlength=0.60mm
\begin{picture}(121.25,41.25)
\put(100.00,40.00){\line(-1,-1){20.00}}
\put(80.00,20.00){\line(1,0){15.00}}
\put(95.00,20.00){\line(1,4){5.00}}
\put(100.00,40.00){\line(1,-4){5.00}}
\put(80.00,20.00){\line(1,-1){20.00}}
\put(100.00,0.00){\line(-1,4){5.00}}
\put(105.00,20.00){\line(-1,-4){5.00}}
\put(100.00,40.00){\circle*{2.50}}
\put(80.00,20.00){\circle*{2.50}}
\put(95.00,20.00){\circle*{2.50}}
\put(105.00,20.00){\circle*{2.50}}
\put(120.00,10.00){\circle*{2.50}}
\put(100.00,0.00){\circle*{2.50}}
\put(100.00,40.00){\line(2,-1){20.00}}
\put(120.00,30.00){\line(-3,-2){15.00}}
\put(105.00,20.00){\line(3,-2){15.00}}
\put(120.00,10.00){\line(-2,-1){20.00}}
\put(120.00,30.00){\circle*{2.50}}
\put(120.00,30.00){\line(0,-1){20.00}}
\put(20.00,40.00){\line(-1,-1){20.00}}
\put(0.00,20.00){\line(1,0){15.00}}
\put(15.00,20.00){\line(1,4){5.00}}
\put(40.00,40.00){\line(1,-4){5.00}}
\put(0.00,20.00){\line(1,-1){20.00}}
\put(20.00,0.00){\line(-1,4){5.00}}
\put(45.00,20.00){\line(-1,-4){5.00}}
\put(20.00,40.00){\circle*{2.50}}
\put(0.00,20.00){\circle*{2.50}}
\put(15.00,20.00){\circle*{2.50}}
\put(45.00,20.00){\circle*{2.50}}
\put(60.00,10.00){\circle*{2.50}}
\put(20.00,0.00){\circle*{2.50}}
\put(40.00,40.00){\line(2,-1){20.00}}
\put(60.00,30.00){\line(-3,-2){15.00}}
\put(45.00,20.00){\line(3,-2){15.00}}
\put(60.00,10.00){\line(-2,-1){20.00}}
\put(60.00,30.00){\circle*{2.50}}
\put(60.00,30.00){\line(0,-1){20.00}}
\put(40.00,40.00){\circle*{2.50}}
\put(40.00,0.00){\circle*{2.50}}
\put(20.00,0.00){\line(0,1){40.00}}
\put(40.00,0.00){\line(0,1){40.00}}
\put(20.00,0.00){\vector(0,1){20.00}}
\put(40.00,0.00){\vector(0,1){20.00}}
\put(70.00,20.00){\makebox(0,0)[cc]{$=$}}
\put(30.00,20.00){\makebox(0,0)[cc]{$+$}}
\put(5.00,5.00){\makebox(0,0)[ct]{$A$}}
\put(60.00,5.00){\makebox(0,0)[ct]{$B$}}
\put(25.00,10.00){\makebox(0,0)[rc]{$e$}}
\put(35.00,10.00){\makebox(0,0)[lc]{$e$}}
\put(120.00,5.00){\makebox(0,0)[ct]{$A +B$}}
\end{picture}
\caption{Edge amalgamation.\label{AmalgFig}}
\end{figure}
Define the {\em edge amalgam of $A$ and $B$ over $f$}---denoted
$A \join{f} B$---to be the
graph obtained from the disjoint union of $A$ and $B$ by 
identifying vertex $f_A(1)$ with $f_B(1)$, vertex $f_A(2)$ with 
$f_B(2)$, and erasing the edges $f_A(e)$ and $f_B(e)$,
see Figure~\ref{AmalgFig}.
The edge amalgam, also called 2--sum in~\cite{Oxley},
is analogous to the symmetric difference of sets, and 
in $A \join{f} B$ we can regard the graph $B - f_B(e)$ as taking 
the place of $f_A(e)$ in $A$, and vice versa.  
Whenever possible, we will indicate the edge functions $f_A$ and 
$f_B$ by simply labeling the edges $f_A(e)$ and $f_B(e)$ the same in
$A$ and $B$, in which case we write $A \join{e} B$ or just 
$A \join{} B$.

It is clear that 
     $A$ and $B$ are $2$-connected if and only if 
     $A \join{f} B$ is $2$-connected.
The edge $f_A(e)$ is called an {\em amalgamated edge} of $A$.
If $X$ denotes the subgraph of $A$ obtained by erasing the 
amalgamated edge, $X$ is also a subgraph of $A \join{f} B$ and 
we write $A = \Bar{X}$. 

    Edge amalgamation is a commutative operation, so 
$A \join{f} B \iso B \join{f} A$.
but it is not in general associative, 
since $ (A \join{f}  B) \join{g} C$ may be rewritten as 
$ A \join{f} (B  \join{g} C ) $
only if $g_{A+B}(e)$ belongs to $B$.
If both expressions are defined, they are equal, and 
note that, since the amalgamated edges are erased, it must be 
true that  $f_B(e) \not = g_B(e)$.  Since the associativity 
is conditional, it is not in 
general possible to simply ignore the parentheses in a long 
expression, in particular  whenever some term has more than two 
amalgamated edges.  A more convenient notation for the result of a 
sequence 
of edge amalgamations, therefore, is a 
labeled tree in which the nodes are labeled with graphs, and 
the edges are labeled with the two functions indicating which edges
are amalgamated in the endpoint graphs.  
Necessarily, the 
amalgamating edges at any node of this tree must be distinct.
We call such a labeled tree $\Tree$ an {\em edge amalgam tree}, and let
$G(\Tree)$ denote the graph obtained from the disjoint union of 
the node labels by amalgamating along the edges determined by the 
edge functions.

To avoid confusion between $G(\Tree)$ and $\Tree$, 
we will hereafter refer to the vertices and edges of 
an edge amalgam tree as {\em nodes} and {\em links}, and  denote them with
Greek as opposed to Roman letters.

    For a finite edge amalgam tree $\Tree$, it is clear that $G(\Tree)$
is $2$-connected if and only if the node graphs are $2$-connected,
and that
$G(\Tree)$ is locally finite if and only if the node 
graphs are locally finite.  
For infinite trees, however, neither is the case, as can be seen
from Figures~\ref{Rotten2Fig} and~\ref{Rotten1Fig}.
Accordingly, we shall give conditions under which an edge amalgam tree
defines a locally finite $2$-connected graph. 




\section{The $3$-block tree}
A graph $G$ is said to be a 
                  {\em $3$-block\/}
       if it contains at least three edges and is either
       a circuit, a finite multilink, or a simple, locally finite
       $3$-connected graph.

Let $\Tree$ be a countable edge amalgam tree. 
We call $\Tree$ a {\em $3$-block tree\/} 
if the following conditions are satisfied:
\begin{enumerate}
     \item If $\{\alpha,\beta\} \in E(\Tree)$ then 
           $G_\alpha$ and $G_\beta$ are not both circuits,
           nor are they both multilinks.
     \item If 
           $\eta = \{\alpha ,\beta\}$ is a link in $\Tree$ amalgamating
           an edge $e$ in $G_\alpha$, 
           then 
           there is a finite subtree $\Tree' \leq \Tree$ with
           $\alpha \in \Tree'$ and  $\beta \not \in \Tree'$,
           and a path in $G(\Tree')$ joining the endpoints of $e$ 
           which is made up entirely of edges unamalgamated
           in $G(\Tree)$.
     \item For each vertex $v$ of $G_\alpha$, 
           $\alpha$ is contained in a finite subtree 
           $\Tree_{v} < \Tree$ such that
           $\starr{v}$ in $G(\Tree_{v})$ consists entirely of
           edges unamalgamated in $\Tree$.
\end{enumerate}

We impose condition~1 since circuits and multilinks would
otherwise have many inequivalent $3$-block trees.
Condition~2 avoids the situation of Figure~\ref{Rotten2Fig}
\begin{figure}[hbt]
     \centering
     \unitlength=0.60mm
     \begin{picture}(125.00,50.25)
          \put(0.00,25.00){\line(0,1){15.00}}
          \put(0.00,40.00){\line(1,0){15.00}}
          \put(15.00,40.00){\line(0,-1){15.00}}
          \put(15.00,25.00){\line(-1,0){15.00}}
          \put(0.00,40.00){\circle*{2.50}}
          \put(0.00,25.00){\circle*{2.50}}
          \put(15.00,25.00){\circle*{2.50}}
          \put(15.00,40.00){\circle*{2.50}}
          \put(25.00,25.00){\line(0,1){15.00}}
          \put(25.00,40.00){\line(1,0){15.00}}
          \put(40.00,40.00){\line(0,-1){15.00}}
          \put(40.00,25.00){\line(-1,0){15.00}}
          \put(25.00,40.00){\circle*{2.50}}
          \put(25.00,25.00){\circle*{2.50}}
          \put(40.00,25.00){\circle*{2.50}}
          \put(40.00,40.00){\circle*{2.50}}
          \put(50.00,25.00){\line(0,1){15.00}}
          \put(50.00,40.00){\line(1,0){15.00}}
          \put(65.00,40.00){\line(0,-1){15.00}}
          \put(65.00,25.00){\line(-1,0){15.00}}
          \put(50.00,40.00){\circle*{2.50}}
          \put(50.00,25.00){\circle*{2.50}}
          \put(65.00,25.00){\circle*{2.50}}
          \put(65.00,40.00){\circle*{2.50}}
          \put(75.00,25.00){\line(0,1){15.00}}
          \put(75.00,40.00){\line(1,0){15.00}}
          \put(90.00,40.00){\line(0,-1){15.00}}
          \put(90.00,25.00){\line(-1,0){15.00}}
          \put(75.00,40.00){\circle*{2.50}}
          \put(75.00,25.00){\circle*{2.50}}
          \put(90.00,25.00){\circle*{2.50}}
          \put(90.00,40.00){\circle*{2.50}}
          \put(100.00,25.00){\line(0,1){15.00}}
          \put(100.00,40.00){\line(1,0){15.00}}
          \put(115.00,40.00){\line(0,-1){15.00}}
          \put(115.00,25.00){\line(-1,0){15.00}}
          \put(100.00,40.00){\circle*{2.50}}
          \put(100.00,25.00){\circle*{2.50}}
          \put(115.00,25.00){\circle*{2.50}}
          \put(115.00,40.00){\circle*{2.50}}
          \put(20.00,30.00){\makebox(0,0)[cc]{+}}
          \put(45.00,30.00){\makebox(0,0)[cc]{+}}
          \put(70.00,30.00){\makebox(0,0)[cc]{+}}
          \put(95.00,30.00){\makebox(0,0)[cc]{+}}
          \put(125.00,30.00){\makebox(0,0)[cc]{$+ \cdots$}}
          \put(0.00,15.00){\line(0,-1){15.00}}
          \put(0.00,0.00){\line(1,0){85.00}}
          \put(0.00,15.00){\circle*{2.50}}
          \put(0.00,0.00){\circle*{2.50}}
          \put(15.00,0.00){\circle*{2.50}}
          \put(15.00,15.00){\circle*{2.50}}
          \put(30.00,15.00){\circle*{2.50}}
          \put(30.00,0.00){\circle*{2.50}}
          \put(45.00,0.00){\circle*{2.50}}
          \put(45.00,15.00){\circle*{2.50}}
          \put(60.00,15.00){\circle*{2.50}}
          \put(60.00,0.00){\circle*{2.50}}
          \put(75.00,0.00){\circle*{2.50}}
          \put(75.00,15.00){\circle*{2.50}}
          \put(0.00,15.00){\line(1,0){85.00}}
          \put(90.00,0.00){\makebox(0,0)[cc]{$\cdots$}}
          \put(90.00,15.00){\makebox(0,0)[cc]{$\cdots$}}
     \end{picture}
     \caption{\label{Rotten2Fig}}
\end{figure}
in which each amalgamation increases the length of a circuit, resulting
in a graph with cut vertices.
Condition~3 insures local finiteness, disallowing amalgamations
such as in Figure~\ref{Rotten1Fig}.
\begin{figure}[hbt]
     \centering
     \unitlength=0.60mm
     \begin{picture}(130.00,55.25)
          \put(15.00,20.00){\line(1,-1){10.00}}
          \put(25.00,10.00){\line(1,1){10.00}}
          \put(35.00,20.00){\line(1,-1){10.00}}
          \put(45.00,10.00){\line(1,1){10.00}}
          \put(55.00,20.00){\line(1,-1){10.00}}
          \put(65.00,10.00){\line(1,1){10.00}}
          \put(75.00,20.00){\line(1,-1){10.00}}
          \put(85.00,10.00){\line(1,1){10.00}}
          \put(95.00,20.00){\line(1,-1){10.00}}
          \put(105.00,10.00){\line(1,1){10.00}}
          \put(115.00,20.00){\line(-1,0){100.00}}
          \put(25.00,10.00){\line(4,-1){40.00}}
          \put(65.00,0.00){\line(4,1){40.00}}
          \put(85.00,10.00){\line(-2,-1){20.00}}
          \put(65.00,0.00){\line(-2,1){20.00}}
          \put(65.00,10.00){\line(0,-1){10.00}}
          \put(15.00,30.00){\line(0,1){10.00}}
          \put(15.00,40.00){\line(1,1){10.00}}
          \put(25.00,50.00){\line(-1,0){20.00}}
          \put(5.00,50.00){\line(1,-2){10.00}}
          \put(15.00,30.00){\line(1,2){10.00}}
          \put(15.00,40.00){\line(-1,1){10.00}}
          \put(40.00,30.00){\line(0,1){10.00}}
          \put(40.00,40.00){\line(1,1){10.00}}
          \put(50.00,50.00){\line(-1,0){20.00}}
          \put(30.00,50.00){\line(1,-2){10.00}}
          \put(40.00,30.00){\line(1,2){10.00}}
          \put(40.00,40.00){\line(-1,1){10.00}}
          \put(65.00,30.00){\line(0,1){10.00}}
          \put(65.00,40.00){\line(1,1){10.00}}
          \put(75.00,50.00){\line(-1,0){20.00}}
          \put(55.00,50.00){\line(1,-2){10.00}}
          \put(65.00,30.00){\line(1,2){10.00}}
          \put(65.00,40.00){\line(-1,1){10.00}}
          \put(90.00,30.00){\line(0,1){10.00}}
          \put(90.00,40.00){\line(1,1){10.00}}
          \put(100.00,50.00){\line(-1,0){20.00}}
          \put(80.00,50.00){\line(1,-2){10.00}}
          \put(90.00,30.00){\line(1,2){10.00}}
          \put(90.00,40.00){\line(-1,1){10.00}}
          \put(115.00,30.00){\line(0,1){10.00}}
          \put(115.00,40.00){\line(1,1){10.00}}
          \put(125.00,50.00){\line(-1,0){20.00}}
          \put(105.00,50.00){\line(1,-2){10.00}}
          \put(115.00,30.00){\line(1,2){10.00}}
          \put(115.00,40.00){\line(-1,1){10.00}}
          \put(5.00,50.00){\circle*{2.50}}
          \put(25.00,50.00){\circle*{2.50}}
          \put(30.00,50.00){\circle*{2.50}}
          \put(50.00,50.00){\circle*{2.50}}
          \put(55.00,50.00){\circle*{2.50}}
          \put(75.00,50.00){\circle*{2.50}}
          \put(80.00,50.00){\circle*{2.50}}
          \put(100.00,50.00){\circle*{2.50}}
          \put(105.00,50.00){\circle*{2.50}}
          \put(125.00,50.00){\circle*{2.50}}
          \put(115.00,40.00){\circle*{2.50}}
          \put(90.00,40.00){\circle*{2.50}}
          \put(65.00,40.00){\circle*{2.50}}
          \put(40.00,40.00){\circle*{2.50}}
          \put(15.00,40.00){\circle*{2.50}}
          \put(15.00,30.00){\circle*{2.50}}
          \put(40.00,30.00){\circle*{2.50}}
          \put(65.00,30.00){\circle*{2.50}}
          \put(90.00,30.00){\circle*{2.50}}
          \put(115.00,30.00){\circle*{2.50}}
          \put(115.00,20.00){\circle*{2.50}}
          \put(95.00,20.00){\circle*{2.50}}
          \put(75.00,20.00){\circle*{2.50}}
          \put(55.00,20.00){\circle*{2.50}}
          \put(35.00,20.00){\circle*{2.50}}
          \put(15.00,20.00){\circle*{2.50}}
          \put(25.00,10.00){\circle*{2.50}}
          \put(45.00,10.00){\circle*{2.50}}
          \put(65.00,10.00){\circle*{2.50}}
          \put(85.00,10.00){\circle*{2.50}}
          \put(105.00,10.00){\circle*{2.50}}
          \put(65.00,0.00){\circle*{2.50}}
          \put(0.00,40.00){\makebox(0,0)[cc]{$\cdots +$}}
          \put(130.00,40.00){\makebox(0,0)[cc]{$+ \cdots$}}
          \put(102.33,40.00){\makebox(0,0)[cc]{+}}
          \put(77.67,40.00){\makebox(0,0)[cc]{+}}
          \put(52.67,40.00){\makebox(0,0)[cc]{+}}
          \put(27.67,40.00){\makebox(0,0)[cc]{+}}
          \put(115.00,10.00){\makebox(0,0)[cc]{$\cdots$}}
          \put(15.00,10.00){\makebox(0,0)[cc]{$\cdots$}}
     \end{picture}
     \caption{\label{Rotten1Fig}}
\end{figure}
Note that we do not require $\Tree$ itself to be locally finite; 
for instance,
one may amalgamate a triangle to each of the edges of 
an infinite locally finite $3$-connected graph (effectively 
subdividing each edge). In order to describe this graph as $G(\Tree$), $\Tree$ 
must be an infinite star.


Note also that, while the edges of $G(\Tree)$ are 
partitioned according to the $3$-blocks to which they belong,
all edges of a particular $3$-block may be amalgamated, in which case
the $3$-block will not correspond to any collection of edges of 
$G(\Tree)$.




\begin{lemma} If $\Tree'$ is a finite subtree of $\Tree$, then $G(\Tree')$
                  is homeomorphic to a subgraph of $G(\Tree)$.
\end{lemma}

\begin{proof} Every edge in $G(\Tree')$ which is not in $G(\Tree)$ is
              amalgamated, so 
              replace each with the path of unamalgamated edges 
              in $G(\Tree) - G(\Tree')$ which is
              guaranteed to exist by condition~2.
\end{proof}

\begin{lemma}
     For any $3$-block tree $\Tree$, 
     $G(\Tree)$ is  locally finite and $2$-connected.
\end{lemma} 

\begin{proof} 
     $G(\Tree)$ is locally finite by condition 3.

     Clearly,  any {\em finite\/} $3$-block tree 
     represents a $2$-connected graph. Let $v$ and $w$ be distinct vertices 
     of $G(\Tree)$, and suppose they correspond to vertices $v'\in G_\alpha$ 
     and $w'\in G_\beta$. Let $\Tree'$ be any finite subtree of $\Tree$ 
     containing $\alpha$ and $\beta$. Then $G(\Tree')$ is $2$-connected, so there 
     are two internally disjoint paths in $G(\Tree')$ from $v'$ to $w'$. Since
     $G(\Tree')$
     is homeomorphic to a subgraph of $G(\Tree)$, there are two such paths 
     joining $v$ and $w$ in $G(\Tree)$, as well.
\end{proof}

It is our aim to prove

\begin{theorem}\label{MainTh}
     Any locally finite $2$-connected graph $G$ corresponds to a
     unique $3$-block tree $\Tree$.
\end{theorem}

We will prove Theorem~\ref{MainTh} in two steps. In the next section, we will 
show how to
construct a particular $3$-block tree for $G$, and in the one following,
we show that this tree is unique.



\section{Existence of $3$-block trees.}


Given a pair of vertices $\{a,b\}$ in a graph $G$, 
there is an equivalence relation 
defined on the edges of $G$ by setting $e$ and $e'$ equivalent if 
there is a path in $G$ containing both $e$ and $e'$, and which has
 neither $a$ nor $b$ as an internal vertex.  
The subgraphs of $G$ which carry the 
equivalence classes are called the {\em \bridges} of $G$ with 
respect to $\{a,b\}$.  Two distinct bridges clearly can intersect only 
at $a$ and $b$, and if $G$ is $2$-connected, their intersection 
is exactly $\{a,b\}$.  $G$ may thus be regarded as the union 
of its bridges along $\{a,b\}$.
However, these bridges may not be themselves $2$-connected.  
If a bridge with respect to $\{a,b\}$ in a $2$-connected graph 
$G$ consists of more than a single edge, 
then adding a new 
edge connecting $a$ and $b$ to that bridge does give a 
$2$-connected graph, and we call these graphs the 
{\em \branches} of $G$ with respect to $\{a,b\}$. 

The {\em deletion of $e$ from $G$}, denoted $G-e$, is the graph
obtained from $G$ by deleting the edge $e$, but not its 
endpoints. The {\em contraction of $e$ in $G$}, denoted
$G \contract e$, is obtained from $G-e$ by identifying the endpoints 
of $e$. 



Let $G$ be a locally finite $2$-connected graph. Choose an arbitrary
edge $e$ of $G$, and let $a$ and $b$ be its endpoints.
We will construct a $3$-block tree $\Tree_e$ with $G(\Tree_e)=G$.

We call $e$  
{\em undeletable} if $G - e$ is $1$-separable, {\em incontractible} if $G 
\contract e$ is $1$-separable, and {\em ordinary} otherwise. 
An edge $e$ cannot be both undeletable and incontractible. since the first
requires that every cycle containing the endpoints of $e$ also contain $e$,
while the second insures two vertices $u$ and $v$ so that every path from
$u$ to $v$ passes through one of the endpoints of $e$, so neither 
the two disjoint
paths from $u$ to $v$ could contain $e$.
Note that 
if $\Tree$ is a $3$-block tree, then condition 3, and the fact that
edge amalgamation does not destroy cutpoints,
guarantees that if the edge 
$e\in G(\Tree)$ belongs to the $3$-block $G_\alpha$, then its 
type---undeletable, incontractible or ordinary---in $G(\Tree)$ 
is the same as its type in $G_\alpha$.

We begin the construction of $\Tree_e$ by defining $\Tree_0$ to consist of a 
single vertex $\alpha_0$ labeled
``$G$,'' with distinguished edge $e$. Then $\Tree_0$ is an edge amalgam tree
(though {\em not\/} a $3$-block tree) and $G=G(\Tree_0)$.


To define $\Tree_1$, we perform what we will call a {\em simple expansion
of the vertex $\alpha_0$ at the edge $e$;} that is, we will replace 
$\alpha_0$ with a star which is an edge--amalgam tree for $G_{v_0}$ (though, 
again, not a  $3$-block tree.)

First, we define the graph $B_e$---the $3$-block of $G$ containing $e$.
This will be the label of the central node of $\Tree_1$. We consider three
cases, depending on the type of the edge $e$.

\begin{itemize}\renewcommand{\labelitemi}{\hspace{\parindent}}
\item \underline{\bf $e$ undeletable.}
In this case, $G-e$ is not $2$-connected, and its block--cutpoint tree is a 
non-trivial path $A_1, v_1, A_2,\ldots,v_{k-1}, A_k$, 
where the vertices $A_i$ correspond to blocks of $G-e$ and the
$v_i$ are the cut vertices of $G-e$.  
Set $v_0$ = $a$ and $v_{k} = b$. Let $B_e$ be the $(k+1)$--cycle with vertices
$v_0,v_1,\ldots,v_k$, and let $\Bar{e_i}$ denote the edge of $B_e$ joining
$v_i$ and $v_{i+1}$ (subscripts modulo $n$.) If some $A_i$ consists of more than
a single edge, we define $\Bar{A_i}$ to be the graph obtained from $A_i$ by
adding an edge $\Bar{e_i}$ joining $v_i$ and $v_{i+1}$.
$G$ is then obtained by amalgamating each $\Bar{A_i}$ 
to $B_e$ along $\Bar{e_i}$, identifying any unamalgamated edges $\Bar{e_i}$
with the corresponding edge in $G$ (see Figure~\ref{UndeletableFig}.)  
\begin{figure}[hbt]
     \centering
     \unitlength=0.80mm
     \begin{picture}(101.00,40.00)
          \put(5.00,15.00){\line(2,1){20.00}}
          \put(25.00,25.00){\line(-4,1){20.00}}
          \put(5.00,30.00){\line(0,-1){15.00}}
          \put(5.00,15.00){\line(1,2){5.00}}
          \put(10.00,25.00){\line(-1,1){5.00}}
          \put(10.00,25.00){\line(1,0){15.00}}
          \put(30.00,5.00){\line(2,3){10.00}}
          \put(40.00,20.00){\line(-3,1){15.00}}
          \put(5.00,0.00){\line(0,1){15.00}}
          \put(5.00,0.00){\circle{2.00}}
          \put(5.00,15.00){\circle{2.00}}
          \put(5.00,30.00){\circle{2.00}}
          \put(10.00,25.00){\circle{2.00}}
          \put(25.00,25.00){\circle*{2.50}}
          \put(30.00,5.00){\circle*{2.50}}
          \put(40.00,20.00){\circle{2.00}}
          \put(25.00,25.00){\line(1,-2){5.00}}
          \put(30.00,15.00){\line(0,-1){10.00}}
          \put(30.00,15.00){\line(2,1){10.00}}
          \put(30.00,15.00){\circle{2.00}}
          \put(60.00,15.00){\line(2,1){20.00}}
          \put(60.00,0.00){\line(0,1){15.00}}
          \put(60.00,0.00){\circle{2.00}}
          \put(60.00,15.00){\circle{2.00}}
          \put(80.00,25.00){\circle{2.00}}
          \put(85.00,5.00){\circle{2.00}}
          \put(60.00,0.00){\line(5,1){25.00}}
          \put(85.00,5.00){\line(-1,4){5.00}}
          \put(55.00,20.00){\line(2,1){20.00}}
          \put(75.00,30.00){\line(-4,1){20.00}}
          \put(55.00,35.00){\line(0,-1){15.00}}
          \put(55.00,20.00){\line(1,2){5.00}}
          \put(60.00,30.00){\line(-1,1){5.00}}
          \put(60.00,30.00){\line(1,0){15.00}}
          \put(55.00,20.00){\circle{2.00}}
          \put(55.00,35.00){\circle{2.00}}
          \put(60.00,30.00){\circle{2.00}}
          \put(75.00,30.00){\circle{2.00}}
          \bezier{104}(55.00,20.00)(70.00,20.00)(75.00,30.00)
          \put(90.00,10.00){\line(2,3){10.00}}
          \put(100.00,25.00){\line(-3,1){15.00}}
          \put(85.00,30.00){\circle{2.00}}
          \put(90.00,10.00){\circle{2.00}}
          \put(100.00,25.00){\circle{2.00}}
          \put(85.00,30.00){\line(1,-2){5.00}}
          \put(90.00,20.00){\line(0,-1){10.00}}
          \put(90.00,20.00){\line(2,1){10.00}}
          \put(90.00,20.00){\circle{2.00}}
          \put(90.00,10.00){\line(-1,4){5.00}}
          \put(5.00,0.00){\line(5,1){25.00}}
          \put(2.50,8.00){\makebox(0,0)[cc]{$e$}}
          \put(52.50,8.00){\makebox(0,0)[cc]{$e$}}
          \put(45.00,10.00){\makebox(0,0)[cc]{$\longrightarrow$}}
     \end{picture}
     \caption{Simple expansion at an undeletable edge.\label{UndeletableFig}}
\end{figure}


{\bf Remark 1.} If $A_i$ is not a single edge then it is $2$-connected
(since it is a block of $G-e$), so  the edge $\Bar{e_i}$ is not undeletable in 
$\Bar{A_i}$.   


\item \underline{\bf $e$ incontractible.}
Let $A_1, \ldots, A_k$ denote the bridges of the endpoints of $e$; there are
only finitely many of them, since $G$ is locally finite. Then 
$k\geq 3$ and one of the $A_i$ is
the edge $e$ itself. If $A_i$ consists of more than a single edge, let 
$\Bar{A_i}$ denote the graph $A_i$ with a new edge $\Bar{e_i}$ joining
$a$ and $b$. 
If $A_i$ is a single edge, set $\Bar{e_i} = A_i$.
Let $B_e$ denote the multilink consisting of $e$ together with all the
edges 
``$\Bar{e_i}$.'' 
$G$ is again the amalgam of $B_e$ with the graphs $\Bar{A_i}$ along the edges 
$\Bar{e_i}$ (see Figure~\ref{IncontractibleFig}.)
\begin{figure}[hbt]
     \centering
     \unitlength=0.80mm
     \begin{picture}(121.00,35.00)
          \put(50.00,15.00){\makebox(0,0)[cc]{$\longrightarrow$}}
          \put(20.00,0.00){\line(0,1){30.00}}
          \put(20.00,30.00){\line(-2,-3){10.00}}
          \put(10.00,15.00){\line(-1,0){10.00}}
          \put(0.00,15.00){\line(4,3){20.00}}
          \put(20.00,0.00){\line(-2,3){10.00}}
          \put(0.00,15.00){\line(4,-3){20.00}}
          \put(20.00,0.00){\line(4,3){20.00}}
          \put(40.00,15.00){\line(-4,3){20.00}}
          \put(20.00,30.00){\line(2,-3){10.00}}
          \put(30.00,15.00){\line(1,0){10.00}}
          \put(30.00,15.00){\line(-2,-3){10.00}}
          \put(0.00,15.00){\circle*{2.00}}
          \put(10.00,15.00){\circle*{2.00}}
          \put(20.00,30.00){\circle*{2.00}}
          \put(20.00,0.00){\circle*{2.00}}
          \put(30.00,15.00){\circle*{2.00}}
          \put(40.00,15.00){\circle*{2.00}}
          \put(80.00,0.00){\line(0,1){30.00}}
          \put(80.00,30.00){\line(-2,-3){10.00}}
          \put(70.00,15.00){\line(-1,0){10.00}}
          \put(60.00,15.00){\line(4,3){20.00}}
          \put(80.00,0.00){\line(-2,3){10.00}}
          \put(60.00,15.00){\line(4,-3){20.00}}
          \put(60.00,15.00){\circle*{2.00}}
          \put(70.00,15.00){\circle*{2.00}}
          \put(80.00,30.00){\circle*{2.00}}
          \put(80.00,0.00){\circle*{2.00}}
          \put(90.00,0.00){\line(0,1){30.00}}
          \put(90.00,30.00){\circle*{2.00}}
          \put(90.00,0.00){\circle*{2.00}}
          \put(100.00,0.00){\line(0,1){30.00}}
          \put(100.00,0.00){\line(4,3){20.00}}
          \put(120.00,15.00){\line(-4,3){20.00}}
          \put(100.00,30.00){\line(2,-3){10.00}}
          \put(110.00,15.00){\line(1,0){10.00}}
          \put(110.00,15.00){\line(-2,-3){10.00}}
          \put(100.00,30.00){\circle*{2.00}}
          \put(100.00,0.00){\circle*{2.00}}
          \put(110.00,15.00){\circle*{2.00}}
          \put(120.00,15.00){\circle*{2.00}}
          \bezier{144}(90.00,0.00)(100.00,15.00)(90.00,30.00)
          \bezier{144}(90.00,0.00)(80.00,15.00)(90.00,30.00)
          \put(22.00,15.00){\makebox(0,0)[cc]{$e$}}
          \put(92.00,15.00){\makebox(0,0)[cc]{$e$}}
     \end{picture}
     \caption{Simple expansion at an incontractible edge.
                 \label{IncontractibleFig}}
\end{figure}


{\bf Remark 2.} Since $A_i$ has a single bridge with respect to 
$\{a,b\}$, $\Bar{e_i}$ is not incontractible in $\Bar{A_i}$.



\item \underline{\bf $e$ ordinary.}
We first define a partial order on the collection of all subgraphs 
$Y_i\subseteq G$ for which $G = \Bar{X_i}\join{}\Bar{Y_i}$ for some $X_i$ 
properly 
containing $e$. Specifically, we set $Y_j \closerthan Y_i$ if 
$Y_i = \Bar{Z}\join{} \Bar{Y_j}$ for some subgraph $Z$. 
Let $\{A_i\}$ denote the collection of maximal elements with respect to this 
partial order, and let $a_i$ and $b_i$ be the vertices of attachment of $A_i$. 


\begin{lemma}\label{IntersectLem}
     Two maximal elements $A_i$ and $A_j$ intersect in at most
     one common vertex of attachment.
\end{lemma}

\begin{proof}
     Let $G=\Bar{X_i}\join{}\Bar{A_i}=\Bar{X_j}\join{}\Bar{A_j}$.
     If $A_i$ and $A_j$ had {\em both\/} vertices of attachment in common,
     then we could write $G=\Bar{X_i\intersect X_j}\join{}\Bar{A_i\union A_j}$,
     and $A_i\union A_j=\Bar{A_i}\join{}\Bar{A_j}$, contrary to the maximality
     of $A_i$ and $A_j$.

     Suppose $A_i$ and $A_j$ have an interior vertex $v$ in 
     common.  Then there are two internally disjoint paths joining
     $v$ and $e$, each passing from $A_i$ to $X_i$ and also from $A_j$ to
     $X_j$. By the above, not both $a_i$ and $b_i$ can belong to $A_i$ nor to
     $A_j$. Choose notation so 
     that the paths are labeled as in Figure~\ref{PathFig}.
     \begin{figure}[hbt]
          \centering
          \unitlength=0.70mm
          \begin{picture}(50.00,45.00)
               \put(5.00,25.00){\line(0,-1){10.00}}
               \put(5.00,15.00){\line(1,-1){10.00}}
               \put(15.00,5.00){\line(1,0){15.00}}
               \put(30.00,5.00){\line(1,1){15.00}}
               \put(45.00,20.00){\line(-1,1){15.00}}
               \put(30.00,35.00){\line(-1,0){15.00}}
               \put(15.00,35.00){\line(-1,-1){10.00}}
               \put(5.00,15.00){\circle*{2.00}}
               \put(5.00,25.00){\circle*{2.00}}
               \put(15.00,35.00){\circle*{2.00}}
               \put(30.00,35.00){\circle*{2.00}}
               \put(45.00,20.00){\circle*{2.00}}
               \put(30.00,5.00){\circle*{2.00}}
               \put(15.00,5.00){\circle*{2.00}}
               \put(0.00,20.00){\makebox(0,0)[cc]{$e$}}
               \put(10.00,40.00){\makebox(0,0)[cc]{$a_i$}}
               \put(10.00,0.00){\makebox(0,0)[cc]{$a_j$}}
               \put(35.00,40.00){\makebox(0,0)[cc]{$b_j$}}
               \put(35.00,0.00){\makebox(0,0)[cc]{$b_i$}}
               \put(50.00,20.00){\makebox(0,0)[cc]{$v$}}
          \end{picture}
          \caption{\label{PathFig}}
     \end{figure}
     Thus $b_j \in A_i$ and $b_i \in A_j$, and every path from 
     any internal vertex of $A_i$ to $e$ which does not pass 
     through $a_i$ must pass through $b_i$, which is in $A_j$.
     Thus, the path must continue through $a_j$, since if it 
     continued through $b_j$, it would still be within $A_i$.
     But then $\{a_i,a_j\}$ separates 
     $A_i \cup A_j$ from $e$, violating the maximality of $A_i$,
     so $A_i$ and $A_j$ have no interior vertex in common.
\end{proof}

In this case, we  form $B_e$ by replacing each  $A_i$ with a new 
edge $\Bar{e_i}$ joining $a_i$ and $b_i$, and we form $\Bar{A_i}$ by 
adding the edge $\Bar{e_i}$ to $A_i$.  It follows from the maximality of
the $A_i$ that $B_e$ is simple (since otherwise a multilink could be split off 
of $B_e$) and that  $B_e$ is $3$-connected (since if there were a two-cutset, 
one of its \bridges\ could be split off of $B_e$.) Further, $B_e$ is locally 
finite since no vertex of $B_e$ has larger valence in $B_e$ than it has in $G$.
Once again, $G$ is the amalgam of $B_e$ 
with the $\{\Bar{A_i}\}$ (see Figure~\ref{OrdinaryFig}.)
\begin{figure}[hbt]
     \centering
     \unitlength=0.80mm
     \begin{picture}(101.00,36.00)
          \put(5.00,25.00){\line(0,-1){20.00}}
          \put(5.00,25.00){\line(3,1){15.00}}
          \put(20.00,30.00){\line(1,-1){15.00}}
          \put(20.00,0.00){\line(-3,1){15.00}}
          \put(5.00,5.00){\line(1,1){10.00}}
          \put(15.00,15.00){\line(-1,1){10.00}}
          \put(15.00,15.00){\line(1,0){20.00}}
          \put(35.00,15.00){\line(-1,3){5.00}}
          \put(30.00,30.00){\line(-1,0){10.00}}
          \put(20.00,0.00){\line(3,1){15.00}}
          \put(35.00,5.00){\line(0,1){10.00}}
          \put(35.00,15.00){\line(-3,-1){15.00}}
          \put(20.00,10.00){\line(0,-1){10.00}}
          \put(20.00,10.00){\line(3,-1){15.00}}
          \put(2.50,15.00){\makebox(0,0)[cc]{$e$}}
       %   \put(5.00,5.00){\vector(0,1){10.00}}
          \put(45.00,15.00){\makebox(0,0)[cc]{$\longrightarrow$}}
          \put(5.00,25.00){\circle*{2.00}}
          \put(5.00,5.00){\circle*{2.00}}
          \put(15.00,15.00){\circle*{2.00}}
          \put(20.00,0.00){\circle*{2.00}}
          \put(20.00,10.00){\circle*{2.00}}
          \put(35.00,5.00){\circle*{2.00}}
          \put(35.00,15.00){\circle*{2.00}}
          \put(30.00,30.00){\circle*{2.00}}
          \put(20.00,30.00){\circle*{2.00}}
          \put(55.00,25.00){\line(0,-1){20.00}}
          \put(60.00,30.00){\line(3,1){15.00}}
          \put(75.00,35.00){\line(1,-1){15.00}}
          \put(85.00,-5.00){\line(-3,1){15.00}}
          \put(55.00,5.00){\line(1,1){10.00}}
          \put(65.00,15.00){\line(-1,1){10.00}}
          \put(65.00,15.00){\line(1,0){20.00}}
          \put(90.00,20.00){\line(-1,3){5.00}}
          \put(85.00,35.00){\line(-1,0){10.00}}
          \put(85.00,-5.00){\line(3,1){15.00}}
          \put(100.00,0.00){\line(0,1){10.00}}
          \put(100.00,10.00){\line(-3,-1){15.00}}
          \put(85.00,5.00){\line(0,-1){10.00}}
          \put(85.00,5.00){\line(3,-1){15.00}}
          \put(52.50,15.00){\makebox(0,0)[cc]{$e$}}
     %     \put(55.00,5.00){\vector(0,1){10.00}}
          \put(55.00,25.00){\circle*{2.00}}
          \put(55.00,5.00){\circle*{2.00}}
          \put(65.00,15.00){\circle*{2.00}}
          \put(85.00,-5.00){\circle*{2.00}}
          \put(85.00,5.00){\circle*{2.00}}
          \put(100.00,0.00){\circle*{2.00}}
          \put(100.00,10.00){\circle*{2.00}}
          \put(85.00,35.00){\circle*{2.00}}
          \put(75.00,35.00){\circle*{2.00}}
          \put(90.00,20.00){\circle*{2.00}}
          \put(75.00,35.00){\circle*{2.00}}
          \put(85.00,15.00){\circle*{2.00}}
          \put(60.00,30.00){\circle*{2.00}}
          \put(70.00,0.00){\circle*{2.00}}
          \put(60.00,30.00){\line(3,-1){30.00}}
          \put(85.00,15.00){\line(-3,1){30.00}}
          \put(55.00,5.00){\line(3,1){30.00}}
          \bezier{144}(70.00,0.00)(75.00,10.00)(100.00,10.00)
     \end{picture}
     \caption{Simple expansion at an ordinary edge.\label{OrdinaryFig}}
\end{figure}
\end{itemize}


 $\Tree_1$ is a star whose central vertex $\beta$ is labeled
``$B_e$,'' and whose pendant vertices $\{\alpha_i\}$ are labeled with the
various $\Bar{A_i}$. Given a link $\eta=\{\beta,\alpha_i\}$ 
in $\Tree_1$, define the
edges $\eta_\beta$ and 
$\eta_{\alpha_i}$ to be the edges $\Bar{e_i}$  in $B_e$ and $\Bar{A_i}$, 
respectively, with the obvious orientations. Clearly, $G=G(\Tree_1)$.

Next, suppose $\Tree_n$ has been defined and 
construct $\Tree_{n+1}$ by performing, for each pendant node $\alpha$
of $\Tree_n$ which is not a $3$-block, 
a simple expansion of $\alpha$ at the edge
$\eta_\alpha$ (where $\eta$ is the unique edge of $\Tree_n$ incident to
$\alpha$).

 Then $G=G(\Tree_{n+1})$,
 and each nonpendant node of $\Tree_{n+1}$ is labeled with
                a $3$-block.  
 Moreover, by remarks~1 and~2 above, 
 no two adjacent nodes of $\Tree_{n+1}$ are labeled with
                  either links or circuits.

Let $\Tree_e=\lim \Tree_n$. 

Let $\Tree^0_n$ denote the edge amalgam tree obtained from 
$\Tree_n$ by removing the pendant nodes which are not $3$-blocks
and let $G^0(\Tree_n)$ be the graph 
obtained from $G(\Tree^0_n)$ by removing the edge $\eta_\alpha$ for each
pendant link $\eta\in\Tree_n$ with endpoint $\alpha\in\Tree^0_n$ (in effect,
we remove from $G(\Tree^0_n)$ all those edges which are amalgamated in
$G(\Tree_e)$).

It is clear
that the $G^0(\Tree_n)$ constitute an increasing sequence of subgraphs of 
$G(\Tree_e)$ and that $\lim G^0(\Tree_n)=G(\Tree_e)$.
It is also clear that the $G^0(\Tree_n)$ are subgraphs of $G$; thus, to 
prove that $G=G(\Tree_e)$, it suffices to show

\begin{lemma} Each finite subgraph of $G$ is contained in $G^0(\Tree_n)$ for
              some $n$.
\end{lemma}

\begin{proof}
   It suffices to show that each edge of $G$ belongs to one of the graphs
   $G_\alpha$ for some node $\alpha\in\Tree$, for then we may choose $n$
   so large that $\alpha$ is a node of $\Tree^0_n$.

   Let $e'$ be any edge of $G$. If $e'\in B_e$, then $e'\in G^0(\Tree_1)$,
   so suppose $e'\not\in B_e$. Let $d$ be the length of a shortest circuit in
   $G$ containing both $e$ and $e'$. Let $\alpha$ be the node of $\Tree_1$
    with $e'\in G_\alpha$, and let $e''=\eta_\alpha$, where $\eta$ is the link of
   $\Tree_1$ connecting $\alpha$ to the central vertex.
   Then the length of a shortest circuit in $G_\alpha$
   containing both $e'$ and $e''$ is either $d$ 
   (if $B_e$ is a multilink) or
   strictly less than $d$ (otherwise). 
   Since two multilinks cannot be adjacent 
   in any $\Tree_n$,
   it follows by induction that $e'$ belongs to $G_\gamma$ for some 
   node $\gamma\in\Tree^0_n$ for some $n$, and since $e'$ is not
   amalgamated, it belongs to $G^0(\Tree_{n+1})$.
\end{proof}

So we have that $G = G(\Tree_e)$, and by the lemma, $\Tree_e$ satisfies
conditions~2 and~3, and so $\Tree_e$ is a $3$-block tree representing $G$.


\section{Invariance of $\Tree_e$}
 
\begin{proposition}
     Let $G$ be a locally finite $2$-connected graph, and let 
     $e$ be an edge of $G$.  If $\Tree$ is any $3$-block tree 
     for $G$, then $\Tree = \Tree_e$.
\end{proposition}

\begin{proof}
     We will show that the $3$-block of $\Tree$ which 
     contains the edge $e$ is equal to $B_e$ in $\Tree_e$.   
     Once this is established, then the subgraphs $A_i$ are 
     determined, and an induction shows that, for all $k$,
     the subtree of $\Tree$
     consisting of all nodes a distance $k$ from the node 
     labeled $B_e$ is identical with the corresponding subtree of 
     $\Tree_e$, and the result follows.

     Let $\alpha$ be the node of $\Tree$ whose graph 
     $G_\alpha$ contains $e$.
     
     If $e$ is undeletable, then  $G_\alpha$ is a cycle 
     $C$, and the internal vertices of $C-e$ correspond to 
     cutpoints of $G-e$. Let $e'$ be an amalgamated 
     edge along this cycle. Then $e'=\eta_\alpha$ for some link $\eta$ with 
     endpoint $\alpha$. Let $\beta$ be the other endpoint of $\eta$. Let $\Tree'$ 
     denote
     the component of $\Tree-\eta$ containing $\beta$, and let $e''=\eta_\beta$.
     Then $e''$ is not undeletable in 
     $G(\Tree')$, since otherwise, $G_\beta$ would be a cycle, as well.
     Therefore, every cutpoint of $G-e$ is a 
     vertex of $C$, and $G_\alpha = C = B_e$. 
     
     If $e$ is incontractible, then  $G_\alpha$ is a multilink, and  each 
     component of $\Tree-\alpha$ corresponds to a union of 
     some of the bridges of the endpoints of $e$.  
     If some such component, say $\Tree'$, corresponds to more than one 
     branch, then its amalgamated edge $e'$ will be incontractible in 
     $G(\Tree')$, and so the $3$-block $G_\beta$ containing
     it is a multilink. But $\beta$ is adjacent to $\alpha$ in $\Tree$, so this
     is impossible.
     Therefore,  each component of $\Tree-\alpha$ 
     corresponds to exactly one \branch, and so $G_\alpha = B_e$.
     
     If $G_\alpha$ is simple, locally finite and $3$-connected,  
     then $e$ is ordinary in $G$. Thus, $B_e$ is also simple, locally 
     finite and $3$-connected. We must show that $B_e=G_\alpha$. 

     Let $\eta$ be a link in $\Tree$ joining $\alpha$ with, say, $\beta$, and
     let $\Tree'$ be the component of $\Tree-\alpha$ containing $\beta$. Then it 
     is clear that the  subgraph $G(\Tree')-\eta_\beta$ of $G(\Tree)$ is
     maximal with respect to the partial order defined earlier, and the same
     is true for every link of $\Tree$ incident with $\alpha$. Since these maximal
     elements are uniquely determined once $e$ has been chosen, it follows that
     $G_\alpha=B_e$.
\end{proof}



\section{Higher connectivity}
\label{HigherSect}

The decomposition of a $2$-connected graph 
into its $3$-block
tree is distinguished from other decompositions of $2$-connected graphs 
by the fact that the $3$-block tree
is uniquely defined.  Thus any symmetry 
exhibited by the graph $\Tree(G)$ will be reflected in the tree $\Tree$.
Specifically, any automorphism of $G(\Tree)$ induces an automorphism of 
$\Tree$.  This is also true in the case of the block-cutpoint tree, 
however, analogous decompositions of graphs of higher connectivity,
see~\cite{OxleyWu}, are not unique.  

\begin{theorem}
   Let $G$ be a simple $1$-connected vertex transitive graph.  
   Then either $G$ is 
   $2$-connected or its block-cutpoint tree is infinite.  
\end{theorem}  


\begin{proof}
   Let $\Tree$ be the block-cutpoint tree.  If $\Tree$ is finite, 
   then it has a center, which is an edge or a vertex.  The center
   cannot be an edge, since the cutpoint corresponding to one of its 
   endpoints would be distinguished in $G$.  
   Similarly, the center cannot
   be a node corresponding to a cutpoint, so the center is a node 
   corresponding to a block.
   Moreover, the central block must contain every vertex of $G$, so
   any other block can at most be a loop, and since $G$ is simple, 
   there is 
   only one block.
\end{proof}

A similar result is also true for $2$-connected graphs.


\begin{theorem}
   Let $G$ be a simple $2$-connected vertex transitive graph.  
   Then either $G$ is 
   either a cycle, $3$-connected or its $3$-block tree is infinite.  
\end{theorem}  


\begin{proof}
   Let $\Tree$ be the $3$-block tree.  If $\Tree$ is finite, 
   then it has a center, which is an edge or a vertex.  The center
   cannot be a link of $\Tree$, since the two endpoints of the amalgamated
   edge corresponding to it would be distinguished, and $G$ is not a 
   multilink.

   Thus the center is a node, and that node cannot represent a
   multilink, since, again, 
   its endpoints would be distinguished in $G$.
   Every vertex of $G$ must be in the $3$-block of the 
   central node, hence every other $3$-block is a mulitlink.  Since $G$ is
   simple, $\Tree$ consists of exactly one $3$-block, hence $G$ is a cycle
   or $3$-connected.
\end{proof}


    The pattern of these two proofs indicates the ``meta-result'' that 
    there cannot be a canonical tree decomposition of $3$-connected
    graphs in analogy with two and one connectivity, 
    since we know there exists 
    infinitely many finite $3$-connected vertex transitive graphs 
    which are not 
    $4$-connected, e.g. the Cayley graphs of finite groups with three 
    generators, and these graphs would have to be indecomposable.   


\medskip
 

\noindent {\small\bf Authors' addresses:}

\noindent {\small 
      James Madison University,
      Harrisonburg, VA 22807,
      cdroms@cayuga.math.jmu.edu
}

\noindent {\small 
      Worcester Polytechnic Institute,
      Worcester, MA 01609-2280,
      bservat@math.wpi.edu
}

\noindent {\small 
      11 Hackfeld Rd,
      Worcester MA 01609,
      jhs@cayuga.math.jmu.edu
}


\begin{thebibliography}{2}
    \bibitem{CunninghamEdmonds}
          W. H. Cunningham and J. Edmonds,
          {\em A combinatorial decomposition theory,}
          Canad. J. Math. \vol{32}, 1980, 734--765.

     \bibitem{DSS95a}
           C. Droms. B. Servatius and H. Servatius,
           {\em Connectivity of Groups,} 
           preprint
           
     \bibitem{DSS95b}
           C. Droms. B. Servatius and H. Servatius,
           {\em Planar Cayley Graphs,} 
           preprint
           
     \bibitem{HopcroftTarjan}
           J. E. Hopcroft and R. E. Tarjan,
           {\em Dividing a graph into triconnected components,} 
           SIAM J. Comput. \vol{3}, 2, 135--158, 1973.
           
           
     \bibitem{Kleitman}
           D. J. Kleitman,
           {\em Methods of investigating the connectivity of large graphs,} 
           IEEE Trans. Circuit  Theory, \vol{16}, 232-233, 1969.

    \bibitem{Oxley} {\rm J. G. Oxley,} {\em Matroid Theory,} 
                    Oxford Univ. Press (1992).

    \bibitem{OxleyWu} 
         J. G. Oxley and H. Wu, 
         {\em On the structure of $3$-connected matroids and graphs,} 
         Preprint, 1995.



     \bibitem{SS95}
           B. Servatius and H. Servatius,
           {\em Self-dual graphs,} 
           to appear in Discrete Math.
           
           
      
    \bibitem{Tutte2} 
          W.\ T.\ Tutte, 
          {\em Connectivity in Graphs,} 
          University of Toronto Press (1966).
                     
     \bibitem{Tutte3}
          W. T. Tutte,
          {\em Connectivity in Matroids},
          Canad. J. Math., \vol{18}, 1966, 1301--1324.

    \bibitem{Tutte1} 
           W.\ T.\ Tutte, 
           {\em Graph Theory,} 
           Encyclopedia of Mathematics,
           Vol.\ 21, Cambridge University Press, Cambridge (1984).

 \bibitem{Whitney}
           H. Whitney,
           {\em $2$-isomorphic graphs,} 
           Amer. J. Math. \vol{55}, 1933, 245--254.


\end{thebibliography}

\end{document} 



          
      James Madison University
      Harrisonburg, VA 22807
      cdroms@cayuga.math.jmu.edu

      Worcester Polytechnic Institute
      Worcester, MA 01609-2280
      bservat@math.wpi.edu

      11 Hackfeld Rd
      Worcester MA 01609
      jhs@cayuga.math.jmu.edu
   


.
