\documentclass{article}
\title{\textbf {\huge {Discrete Complex Analysis}}}
\author{Karen Perry}
%\email{kperry@cc.usu.edu}
\date{August 4, 2003}

% Check if we are compiling under latex or pdflatex, and include the
% appropriate graphics package
\ifx\pdftexversion\undefined
  \usepackage[dvips]{graphicx}
\else
  \usepackage[pdftex]{graphicx}
\fi

\usepackage{amsmath}
\usepackage{amssymb}

% Define the theorem environments
\usepackage{amsthm}
\newtheorem{theorem}{Theorem}[section] % numbered like the section
\newtheorem{lemma}[theorem]{Lemma} % numbered like the theorems
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition} % styled differently... not italicized
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{remark}[theorem]{Remark}
% Let \sign show roman-style characters in math mode
\newcommand{\sign}{\mathop{\mathrm{sign}}}

%\raggedbottom % Makes the bottom margin more flexible (helpful for pictures)

\begin{document}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Abstract
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
In the continuous case, a $\gamma$-harmonic function $u(x,y)$ is a function which satisfies the equation $\mathrm{div}(\gamma \nabla u)=0$.  Curtis and Morrow, \cite{CM}, defined a $\gamma$-harmonic function $u(p)$ on a discrete electrical network as one that satisfies $\sum\limits_{q\in N(p)}\gamma_{pq}(u(p)-u(q))=0.$

This paper discusses discretizations of other functions that are already defined in the continuous case.  Specifically it defines a Poisson Integral Formula, a Cauchy-Riemann equation, a harmonic conjugate of a discrete harmonic function, and an analytic function on an electrical network.  The discussion of discrete Cauchy-Riemann equations leads to a study of dual graphs, so two main ideas about dual graphs are presented.  There is an algorithm for recovering the values of a harmonic conjugate given the values of a harmonic function.  Additionally, there is a theorem describing when a graph and its dual are Y-$\Delta$ equivalent.  
\end{abstract}

\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Introduction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
To begin a study of discretizations on electrical networks, this paper must first define an electrical network.  
A $\textit{graph with a boundary}$ is a graph consisting of a set of nodes $V$, and edges $E$ connecting those nodes, with certain of those nodes designated as boundary nodes $V_B$, and the other nodes representing interior nodes $V_I$.  A $\textit{circular planar graph with boundary}$, $G$, is a graph with boundary embedded in a disc so that the boundary nodes lie on the circle, $C$, which bounds the disc, and the rest of the graph is interior to the disc.  The vertices of the graph are numbered in the following manner.  Start by numbering the boundary vertices, in counter-clockwise order around the circle $C$, then number the interior vertices.  

Graphs are useful in representing networks of resistors.  An $\textit{electrical network}$ $\Gamma = (G, \gamma)$ is a graph with a boundary $G$ together with a function $\gamma > 0$ defined on the edges of $G$ which specifies the conductivity of each edge.  Let $u(p)$ be a vertex function that defines the potential at each node of the network $\Gamma$.  A function $u(p)$ is said to be $\gamma \textit{-harmonic}$ if it satisfies the equation 
\begin{equation}
\sum\limits_{q\in N(p)}\gamma_{pq}(u(p)-u(q))=0
\end{equation}
for all $p \in V_{I}$, where $N(p)$ is the set of nodes that are neighboring $p$, that is, there is an edge between $p$ and each node in $N(p)$.  Saying that a potential function $u(p)$ is $\gamma$-harmonic on the interior of $\Gamma$ is equivalent to saying that the net current flowing into each interior node is zero.  

The Kirchhoff matrix, $K$, is a useful tool for working with electrical networks.  It stores the values of the conductances of the edges in the network.  Entries in the \textit{Kirchhoff matrix} for an electrical network are defined by 
  \begin{enumerate}
    \item $K_{i,j} = -\gamma_{ij}$ for $i \ne j$
    \item $K_{i,i} =  \sum_{j \ne i} \gamma_{ij}$
  \end{enumerate}
where $\gamma_{ij}$ is the conductance of the edge between node $i$ and node $j$.  If there is no edge between $i$ and $j$, the conductance $\gamma_{ij}$ is zero.  The Kirchhoff matrix can be written in block form: 
  \begin{equation}
    K =  \begin{bmatrix}
           A  &  B \\
           B^{T} &  C
         \end{bmatrix}
  \end{equation}
where $A$ stores conductances of edges between two boundary nodes, $C$ stores conductances of edges between two interior nodes, and $B$ stores conductances for boundary to interior edges.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  The Discrete Poisson Integral Formula
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Discrete Poisson Integral Formula}
In the continuous case, the Poisson Integral Formula is a tool for solving Dirichlet boundary value problems.  The Dirichlet boundary value problem is to find a function $u$ that is harmonic on the interior of a region given only the values of $u$ on the boundary of that region.  The generalized Poisson Integral Formula says that given boundary data $u|_{\partial D} = \phi (w)$, interior values of $u$ can be calculated by 
\begin{equation}
u(z) = - \int \limits_{\partial \Omega} \frac{1}{2\pi} \frac{\partial G(z,w)}{\partial n_w} \phi (w)  ds(w)
\end{equation}
where $G(z,w)$ is the appropriate Green's Function.  A Green's function for a domain with singularity at $p$ is a function $G(z,p)$ such that 
  \begin{enumerate}
     \item $G(z,p)$ is harmonic for $z$ in domain $\Omega$ when $z \ne p$,
     \item $G(z,p) + log|z-p|$ is harmonic near $p$, and
     \item $G(z,p) = 0$ if $z$ is on the boundary of the domain $\partial \Omega$.
  \end{enumerate}

The Dirichlet problem on an electrical network, $\Gamma$ is to find a function $u$ that is $\gamma$-harmonic on the interior of $\Gamma$ given only the values of $u$ on the boundary, $u|_{V_B} = \phi$.  The Dirichlet problem written in equation form is
\begin{equation}\label{Dirichlet}
  \begin{bmatrix}
    A  &  B \\
    B^{T} &  C
  \end{bmatrix}
  \begin{bmatrix}
    \phi \\ u|_{V_I}
  \end{bmatrix}
 =\begin{bmatrix}
    * \\ 0
  \end{bmatrix}
\end{equation}
where $*$ represents some current on the boundary.  This equation merely states that conductivities (stored in the Kirchhoff matrix) times voltages equals currents.  Also the zero in the equation says that $u$ is harmonic, that is, the net current flow at every interior node is zero.  The voltages on the boundary are specified by the function $\phi$.  

\begin{claim}
The discrete analog of the Poisson Integral Formula is 
\begin{equation}\label{discretePIF}
  u|_{V_I} = -C^{-1} B^{T} \phi
\end{equation}
because 
\begin{enumerate}
  \item the equation solves the Dirichlet Problem (\ref{Dirichlet})
  \item $C^{-1}$ acts like a Green's Function where the arguments of the Green's Function are the rows and columns of the matrix
  \item the equation contains discrete analogs of an integral around the boundary and a normal derivative of the Green's Function times the given boundary data $\phi$.
\end{enumerate}
\end{claim}

Simple block-matrix multiplication of (\ref{Dirichlet}) gives the equation
\begin{equation}
B^T \phi + C u = 0
\end{equation}
This equation has a unique solution given by (\ref{discretePIF}) if and only if $C$ is invertible.  Lemma 3.8 in \cite{CM} proves that $C$ is invertible, so part 1 of the claim is verified.

A discrete Green's function for a domain $D$ with a singularity at $p$ is a function $G(z,p)$ such that
\begin{enumerate}
\item $G(z,p)$ is harmonic for $z$ in $D$, $z \ne p$,
\item $G(z,p)$ is not harmonic at node $p$, instead there is a current source of magnitude 1 at $p$, and
\item $G(z,p) = 0$ if $z$ is in the boundary $\partial D$
\end{enumerate}

Given this definition of a discrete Green's function, a Green's function $g(z,p)$ on the electrical network $\Gamma$ must equal zero for nodes on the boundary, \\ $g(z,p)|_{z \in \partial D} = 0$ and satisfy
\begin{equation}
C g(z,p)|_{z \in int} = \begin{bmatrix} 0, \dots, 0, 1, 0, \dots, 0, \end{bmatrix}^{T}
\end{equation}
for nodes in the interior, where the 1 in the right side of the equation is in the $p^{th}$ position representing a current source of 1 there.  Solve the equation for $g(z,p)$ to get
\begin{equation}
g(z,p)|_{z \in int} = C^{-1} \begin{bmatrix} 0, \dots, 0, 1, 0, \dots, 0 \end{bmatrix}^{T} 
\end{equation}
Therefore, the desired Green's function is stored in the $p^{th}$ column of $C^{-1}$, and part 2 of the claim is verified.

The expression for the $p^{th}$ entry of the solution $u$ can be written as
\begin{equation}
u(p) = -\sum \limits_{j} C^{-1}(p,j) (B^{T}\phi)_{j}
\end{equation}
Expanding $(B^{T}\phi)_{j}$ gives
\begin{equation}
u(p) = -\sum \limits_{j} \Bigl( C^{-1}(p,j) \sum \limits_{i} (B^{T}(j,i) \phi_{i}) \Bigr)
\end{equation}
Rearraging the order of summation yields
\begin{equation}
u(p) = -\sum \limits_{i} \Bigl[ \Bigl( \sum \limits_{j} C^{-1}(p,j) B^{T}(j,i) \Bigr) \phi_{i} \Bigr]
\end{equation}
$C^{-1}$ is symmetric, so rewrite $C^{-1}(p,j)$ as $C^{-1}(j,p)$.  However, the columns of $C^{-1}$ are simply the Green's functions so rewrite $C^{-1}(j,p)$ as $g(j,p)$.  Furthermore, by the definition of the Kirchhoff matrix, $B^{T}(j,i)= -\gamma_{ij}$.  The summation over $i$ indexes the columns of $B^{T}$ so $i$ indexes boundary nodes.  Since Green's functions are zero on the boundary of the region, $g(i,p)$ is zero when $i$ refers to a boundary node.  Thus inserting a $g(i,p)$ into the equation makes no difference.  With these changes, the equation becomes
\begin{equation}
u(p) = \sum \limits_{i} \Bigl[ \Bigl( \sum \limits_{j} \gamma_{ij} (g(i,p) - g(j,p)) \Bigr) \phi_{i} \Bigr]
\end{equation}

The summation over $i$ corresponds to the integral over the boundary in the Poisson Integral Formula.  The function $\phi$ corresponds to the boundary conditions.  $\sum_{j} \gamma_{ij} (g(i,p) - g(j,p))$ is the normal derivative of the Green's function.  Therefore part 3 of the claim is verified. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  The gamma CR eqns
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The $\gamma$-Cauchy-Riemann Equations}

We now have discrete analogs for harmonic functions and for the Poisson Integral formula defined on electrical networks.  A logical next area of study would be to find a discrete analog of the Cauchy Riemann equations and a discrete analog of an analytic function on an electrical network.

In order to make use of the Cauchy-Riemann equations on electrical networks with conductivities $\gamma$, I first have to consider if there is a pair of Cauchy-Riemann equations that involve a variable $\gamma$ in the equations.  

Given a function, $f(z)=u(x,y)+i \times v(x,y)$, of a complex variable $z=x+iy$, the Cauchy-Riemann Equations are $u_{x} = v_{y}$ and $u_{y} = -v_{x}$.  If the pair of real-valued functions $u$ and $v$ satisfy those equations, the functions are harmonic, and the complex function $f(z)$ is analytic.  

I define the $\gamma$-Cauchy-Riemann equations as follows:
\begin{gather} 
\gamma u_{x} = v_{y}\label{gammaCR1}\\
\gamma u_{y} = -v_{x}\label{gammaCR2}
\end{gather}

\begin{theorem}
If a pair of real-valued functions $u(x,y)$ and $v(x,y)$ satisfy the $\gamma$-Cauchy-Riemann equations, then $u(x,y)$ is $\gamma$-harmonic, and $v(x,y)$ is $1/ \gamma$-harmonic.
\end{theorem}

\begin{proof}
Take the derivative of equation $\eqref{gammaCR1}$ with respect to $x$: $(\gamma u_x)_x = (v_y)_x$.
Take the derivative of equation $\eqref{gammaCR2}$ with respect to $y$: $(\gamma u_y)_y = (-v_x)_y$.
Adding the two equations yields $(\gamma u_x)_x + (\gamma u_y)_y = 0$.  Therefore, $u$ is $\gamma $-harmonic.

To prove that $v$ is $(1/\gamma )$-harmonic, rewrite $\eqref{gammaCR1}$ as $u_x = (1/\gamma ) v_y$, and rewrite $\eqref{gammaCR2}$ as $-u_y = (1/\gamma ) v_x$.  Then taking the proper partial derivatives and adding the two equations gives $((1/\gamma ) v_y)_y +((1/\gamma ) v_x)_x = 0$  Therefore, $v$ is $1/\gamma$-harmonic.  
\end{proof}

When $\gamma = 1$, the $\gamma$-Cauchy-Riemann equations reduce to the normal Cauchy-Riemann equations.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Another form of the c-r eqns
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Another Form of the Cauchy-Riemann equations}
The Cauchy-Riemann equations are related to rotations in the complex plane.  The equation $u_{x} = v_{y}$ equates a directional derivative in the $x$ direction with a directional derivative in the $y$ direction.  The equation $u_{y} = -v_{x}$ equates a directional derivative in the $y$ direction with a directional derivative in the $-x$ direction.  

Rather than taking the directional derivatives in the Cauchy-Riemann equations in the $x$ and $y$ directions, one can take derivatives in the normal and tangential directions.  If you have an arbitrary normal vector $n = a + bi = (a,b)$, you can rotate it 90 degrees to the left in the complex plane by multiplying it by $i$.  

%%%%%%%%%%%%%%%%%%%% A Picture, n and tau %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=6cm]{nAndTau.eps}
%\caption{}
\end{center}
\end{figure}

Thus we can let $\tau = i n = -b + ai = (-b, a)$.  Then the Cauchy-Riemann equations can take the following form: 

\begin{theorem}
If two functions u and v satisfy
\begin{gather*} 
u_{x} = v_{y}\\
u_{y} = -v_{x}
\end{gather*}
then they satisfy
\begin{gather*}
\partial u/\partial n = \partial v/\partial \tau \\
\partial u/\partial \tau = -\partial v/\partial n 
\end{gather*}
where $n$ is a vector $a + bi$ and $\tau$ is a vector rotated 90 degrees counter-clockwise, $-b + ai$.  
\end{theorem}

\begin{proof}
Assume that u and v satisfy the Cauchy-Riemann equations.  Also write $n = (a,b)$ and $\tau = (-b, a)$.  I can write the directional derivative $\partial u/\partial n$ as a dot product of the gradient with the normal vector n: $\nabla u \cdot n$.  Then
  \begin{equation*}
  \begin{split}
  \partial u/\partial n & = \nabla u \cdot n \\
  & = (u_x , u_y) \cdot (a,b)\\
  & = u_x  a + u_y  b\\
  & = v_y  a + -v_x  b \\
  & = (v_x, v_y) \cdot (-b, a)\\
  & = \nabla v \cdot \tau \\
  & = \partial v/\partial \tau
  \end{split}
  \end{equation*}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Dual Graphs and the Discrete Cauchy Riemann Equation
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{sloppypar}
\section{Dual Graphs and the Discrete Cauchy Riemann Equation}
\end{sloppypar}
To make use of the $\gamma$-Cauchy-Riemann equations on planar electrical networks, I first present some definitions.  \\

\begin{definition}
The dual graph, $G_\bot$, of a circular planar graph with boundary, $G$, is a circular planar graph with boundary drawn in the following manner.  The graph $G$ together with the circle $C$ partition the disc into a finite number of disjoint cells.  The vertices of the dual graph are defined by placing a vertex in each cell.  If one of the edges of a cell is an arc of $C$, place the vertex on this arc.  For each edge in the original graph, there is one edge in the dual graph that intersects the original edge and connects the two vetices drawn in the adjacent cells.  
\end{definition}

If a network $\Gamma = (G, \gamma)$ has conductivities $\gamma$ then its dual $\Gamma_{\bot} = (G_{\bot}, \frac{1}{\gamma})$ has conductivities $\frac{1}{\gamma}$.

%%%%%%%%%%%%%%%%%%%%Another Picture, Original and Dual Graph %%%%%%%%%%%%%%%%
\begin{figure*}[h]
\begin{center}
\includegraphics[width=9cm]{dualGraph2.eps}
\caption{Original Graph and Dual Graph}
\end{center}
\end{figure*}


\begin{definition}
Let \(u(p)\) be a vertex funtion defined on the vertices of the original graph $G$, and let \(v(p)\) be a vertex function defined on the vertices of the dual graph $G_{\bot}$.  Let $e$ be an edge in the original graph $G$ with endpoints $p$ and $q$.  Orientation $e$ as $\overrightarrow{qp}$ Let $e_{\bot}$ be the intersecting edge in the dual graph $G_{\bot}$ with $p'$ the endpoint of $e_{\bot}$ that is reached by starting at $p$ and traveling counter-clockwise, and $q'$ being the opposite endpoint of $e_{\bot}$, as shown in figure $\ref{dualEdge}$.  Orient $e_{\bot}$ as $\overrightarrow{q'p'}$.  Let $\Delta _{e} u = u(p) - u(q)$ and let $\Delta_{e_{\bot}}v = v(p')-v(q')$
Then the $\gamma$ $\textit{-Cauchy-Riemann equation}$ on an electrical network is 
\begin{equation}
\gamma_{e} \times \Delta _{e} u = \Delta_{e_{\bot}}v
\end{equation}
\end{definition}

%%%%%%%%%%%%%%%%%%%Picture, Edge and Dual Edge %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=9cm]{dualEdge.eps}
\caption{Original Edge and Dual Edge}\label{dualEdge}
\end{center}
\end{figure}

\begin{remark}
The $\gamma$-Cauchy-Riemann equation is independent of the orientation chosen for edge $e$.
\end{remark}

\begin{theorem}
If vextex functions $u$ and $v$, defined on $G$ and $G_\bot$ respectively, satisfy the discrete $\gamma$-Cauchy-Riemann equation, then $u$ is $\gamma$-harmonic, and $v$ is $\frac{1}{\gamma}$-harmonic, that is, $\sum_{q\in N(p)}\gamma_{pq}(u(p)-u(q)) = 0$ \\and $\sum_{q'\in N(p')}\frac{1}{\gamma}_{p'q'}(v(p')-v(q')) = 0.$
\end{theorem}

\begin{proof}
If $u$ and $v$, defined on $G$ and $G_\bot$ respectively, satisfy the discrete $\gamma$-Cauchy-Riemann equation, then fix a point $p$ in $G$.  Point $p$ is connected by edges to certain other vertices in the graph $q_1, q_2, ..., q_n$.  Call $e_j$ the edge between $p$ and $q_j$.  Let $e_{\bot {j}}$ denote the edge in the dual graph $G_\bot$ that intersects $e_j$.  The edges $e_{\bot {j}}$ form a closed path in the dual graph.  The sum $\sum \limits_{j=1}^{n} \Delta_{e_{\bot {j}}}v$ over all the edges in that path is identically zero because it forms a telescoping series with all the terms cancelling out.  Thus,
  \begin{equation*}
  \begin{split}
    \sum\limits_{q\in N(p)}\gamma_{pq}(u(p)-u(q))&= \sum \limits_{j=1}^{n}\gamma_{e_j}         \Delta_{e_j} u \\
    &= \sum \limits_{j=1}^{n}\gamma_{e_j}(1/\gamma_{e_j} \times \Delta_{e_{\bot {j}}}v)\\
    &= \sum \limits_{j=1}^{n} \Delta_{e_{\bot {j}}}v\\
    &= 0
  \end{split}
  \end{equation*}

The proof that $v$ is $\frac{1}{\gamma}$-harmonic is left to the reader.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Green's Theorem
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Green's Theorem}
  
\begin{definition}
An {\it edge function} is a function $f(e)$ defined on an edge $e$ such that $f(-e) = -f(e)$.  
\end{definition}

Let $F(e)$ be an edge function.  Green's Theorem takes the following form.

\begin{theorem}
Let $D$ be a connected region in a graph $G$ made of vertices and edges in $G$, bounded by a simple closed curve $\partial D$.

Let $e\succ p$ denote an edge $e$ with $p$ as one of its endpoints.  Let $e\leftarrow \partial D$ denote that $e$ is an outward-pointing edge normal to $\partial D$ with one endpoint of $e$ on $\partial D$.

Then $\sum \limits_{p\in D} \sum \limits_{e\succ p} F(e) = \sum \limits_{e\leftarrow \partial D} F(e)$.
\end{theorem}

\begin{proof}
Let group 1 be the set of edges with both its endpoints in the region $D$, and let group 2 be the set of edges with one endpoint on $\partial D$ and the other endpoint outside of the region $D$.  
If an edge $e$ is in group 1, then both $e$ and $-e$ are included in the sum $\sum \limits_{p\in D} \sum \limits_{e\succ p} F(e)$.  However, $F(e) + -F(-e) = 0$, so the sum reduces to a sum of edges in group 2, that is, $\sum \limits_{e\leftarrow \partial D} F(e)$.
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Harmonic Conjugates
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Harmonic Conjugates}
\begin{definition}
Given a $\gamma$-harmonic function $u$, a function $v$ that satisfies  $\gamma_{e} \times \Delta _{e} u = \Delta_{e_{\bot}}v$ is called a $\textit{harmonic conjugate}$ of $u$.
\end{definition}

The following theorem must be proved before proving the existence of the harmonic conjugate.  

\begin{theorem}
Suppose f is an edge function on a connected graph G.  Further suppose that $\sum \limits_j f(e_j) = 0$ for all closed curves in G denoted by a sequence of edges ($e_1, e_2, ..., e_n$).  Then there exists a vertex function $w$ such that $f = \nabla w$.  
\end{theorem}

\begin{proof}
Fix a point in a graph $p_0$.  Let $w(p_0) = 0$.  Since G is connected, we can find a path from $p_0$ to an arbitrary point $q$.  Define a function on this arbitrary point as $w(q) = \sum f(e_j)$ where the sum is over all edges $e_j$ in a path from $p_0$ to $q$.  We must now show that the function $w(q)$ has a unique value at any point in the graph.  Find a second path from $p_0$ to $q$.  Since by the hypotheses of the theorem, the sum of $f(e_j)$ around a closed path equals zero, the sum taken along the first path from $p_0$ to $q$ plus the sum taken backwards along the second path back to $p_0$ must equal zero.  However, this implies that $w(q)$ evaluated on the first path is the same as the value of $w(q)$ taken along the second path.  Then $w(q)$ is uniquely defined.  Furthermore, $f(e_{pq})=w(q)-w(p)$.
\end{proof}

\begin{theorem}
Given a $\gamma$-harmonic function $u$ on an electrical network, a harmonic conjugate $v$ always exists.
\end{theorem}

\begin{proof}
Define an edge function of the dual graph $F(e_{\bot}) = \gamma_e \Delta_e u$.  Let $S_\bot$ be any closed path in $G_{\bot}$.  Let $S$ be the set of edges in the original graph crossing $S_\bot$.  Let $T$ be the region in the original graph bounded by the closed path $S_\bot$.  Then 
\begin{equation}
\sum \limits_{e_j  \in S_{\bot}} F(e_{\bot_j}) = \sum \limits_{e_j \in S} \gamma_j \Delta_{e_j} u
\end{equation}
The right-hand side of the above equation represents the currents flowing out of edges in $S$.  By Green's Theorem, this equals 
\begin{equation}
\sum \limits_{e_j \in S} \gamma_j \Delta_{e_j} u = \sum \limits_{p\in T} \sum \limits_{e\succ p} \Delta_{e} u
\end{equation}
This sum of currents is also equal to the sum of net current flowing out of each node in the whole region $T$.  But since $u$ is $\gamma$-harmonic, this sum equals zero.  Then by the previous theorem, there exists a vertex function $v$ such that $F(e_{\bot})=\Delta v$.
\end{proof}

\begin{remark}
Given a $\gamma$-harmonic function $u$ on an electrical network, the harmonic conjugate $v$ is unique up to a constant.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Discrete Analytic Functions 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Discrete Analytic Functions}
I can now give a definition for an analytic function on a discrete planar electrical network.
\begin{definition}
A $\gamma$ analytic function $f = (u,v)$ is a pair of functions $u$ and $v$ such that $u$ is a $\gamma$-harmonic vertex function defined on a graph $G$, and
$v$ is a $\frac{1}{\gamma}$ harmonic vertex function defined on the dual graph $G_{\bot}$, and
$u$ and $v$ satisfy the discrete $\gamma$-Cauchy-Riemann equation, $\gamma_{e} \times \Delta _{e} u = \Delta_{e_{\bot}}v$.
\end{definition}

%Another way to think of an analytic function is to look at the medial graph of the original graph.  In a medial graph, the black cells correspond to vertices in the original graph where u(p) is defined.  The white cells correspond to vertices in the dual graph where v(p) is defined.  Thus the analytic function is defined on the whole plane.  Note that the discrete Cauchy-Riemann equation must be enforced at the corners of the cells.

In the continuous case, a function that is analytic satisfies the Cauchy Integral Theorem, 
\begin{equation}
 \int_C f(z)dz = 0
\end{equation}
I would like to be able to express a discrete analog of the Cauchy Integral Theorem on a discrete electrical network, but have been unable to do so yet.

I can make a simple observation regarding closed curves on $G$ or $G_\bot$.  This integral theorem takes the following form.  Take a simple closed curve C on a graph G and label all of the edges on the closed curve $e_1,...,e_n$.  Each edge $e_i$ is intersected by an edge $e_{\bot i}$ in the dual graph.  Label the vertex of $e_{\bot i}$ outside of C as $q_j^+$ and the vertex of $e_{\bot i}$ inside of C as $q_j^-$.  Then $\sum\limits_{j} \frac{1}{\gamma}_j~\times~(v(q_j^+) - v(q_j^-)) = 0$.
% the ~ keeps Latex from allowing a space between these two characters


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Recovering Potentials on $G_{\bot}$ from Potentials on $G$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Recovering Potentials on $G_{\bot}$ from Potentials on $G$ }
The study of Cauchy-Riemann equations and analytic functions of electrical networks led to a study of dual graphs.  To better understand dual graphs, two main ideas about dual graphs are discussed in the following sections.  First, given a harmonic function $u$ on an original graph $G$, can $u$'s harmonic conjugate be written in terms of the Kirchhoff matrix?  Second, when are $G$ and $G_{\bot}$ electrically equivalent?

Let $u$ be a $\gamma$-harmonic function on $G$.  Let$\phi = u|_{\partial G}$.  Let $v$ be a harmonic conjugate of $u$.  Let $\psi = v|_{\partial G_{\bot}}$.  In the following we will describe $\psi$ in terms of $\phi$ and $v$ in terms of $\psi$.  To express this relationship, I first need to define the \textit{response matrix} and the \textit{integral matrix}.

\begin{definition}
The response matrix is the matrix $\Lambda_\gamma$ calculated from the Kirchhoff matrix by
\begin{equation}
\Lambda_{\gamma} = A - BC^{-1}B^{T}
\end{equation}
Premultiplying a vector of potentials on the boundary nodes of a graph by the response matrix gives a vector of currents flowing into the boundary nodes of the graph.  
\end{definition}

\begin{definition}
The \textit{integral matrix}, $T_n$, is an $n \times n$ matrix with 1's in all the entries on or below the main diagonal, and 0's elsewhere.  Pre-multiplying a vector $x = (x_1, x_2, ..., x_n)^{T}$ by the integral matrix gives ``integrals", or sums, of the entries in the original vector:
\begin{equation*}
T_n x = \begin{bmatrix} x_1 \\ x_1 + x_2 \\ ... \\ x_1 + ... + x_n \end{bmatrix}
\end {equation*}
\end{definition}

\begin{theorem}
Let $\phi$ be defined on $\partial G$.  Then $\phi$ uniquely determines a $\gamma$-harmonic function $u$ on $G$.  The boundary values of a harmonic conjugate $v$ of $u$ are given by the equation
  \begin{equation}
    \psi = T \Lambda_{\gamma} \phi
  \end {equation}
and $v$ on the interior nodes of $G_{\bot}$ is given by the equation
  \begin{equation}
    v = -C_{\bot}^{-1} B_{\bot}^{T} (T \Lambda_{\gamma} \phi)
  \end{equation}
\end{theorem}

\begin{proof}

First consider the current $I_1$ flowing out of vertex 1.  Denote the vertex 1 as $p_1$.  Current is given by conductance times the drop in voltage:
\begin{equation}\label{current}
I_1 = \sum \limits_{q \in N(p_1)} \gamma_{1q}(u(p_1) - u(q))
\end{equation}
Let $P$ be the collection of edges in the dual graph that intersect all the edges incident to $p_1$ in the original graph, as shown in figure \ref{pathP}.  A sum of voltage drops across each edge in $P$ will collapse to simply the voltage of the first node in $P$ minus the voltage of the last node in $P$, $v(p_{\bot 1})-v(p_{\bot n})$.  Since $\gamma \Delta u = \Delta v$, we also know that 
\begin{equation}\label{current2}
I_1 = \sum \limits_{q \in N(p_1)} \gamma_{1q}(u(p_1) - u(q)) = \sum \limits_{P} (v(p') - v(q')) = v(p_{\bot 1})-v(p_{\bot n})
\end{equation}
Solving for the potential at $p_{\bot 1}$ reveals that $v(p_{\bot 1}) = I_1 + v(p_{\bot n})$.  Since the $v$ function is uniquely determined only up to a constant, I can arbitrarily assign $v(p_{\bot n})$ to be equal to 0, then $v(p_{\bot 1}) = I_1$.

%%%%%%%%%%%%%%%%%%%Picture, Path P %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=7cm]{cow.eps}
\caption{Finding potentials in the dual graph}\label{pathP}
\end{center}
\end{figure}


I can inductively prove that the potential at any boundary vertex $p_{\bot k}$ is the sum of currents in $G$, $I_1 + ... + I_k$.  I already showed the case for k = 1.  Assume this statement is true for an arbitrary k.  Let $P_{k+1}$ be the collection of edges in the dual graph that intersect all the edges incident to $p_{k+1}$ in the original graph.  Then
\begin{equation}  
\begin{split}
v(p_{\bot (k+1)})& = v(p_{\bot k}) + \sum_{P_{k+1}} v(p') - v(q')  \\
               & = v(p_{\bot k}) +\sum \limits_{q \in N(p_k)} \gamma_{1q} (u(p_{k+1}) - u(q))\\
               & = v(p_{\bot k}) + I_{k+1} \\
               & = \sum \limits_{j = 1}^{k} I_j + I_{k+1}\\
               & = \sum \limits_{j = 1}^{k+1} I_j
\end{split}
\end{equation}

From the definition of the response matrix $\Lambda_{\gamma}$, we know that $\Lambda_{\gamma} \phi$ is a vector of the currents flowing into the boundary nodes of $G$.  The potentials at the boundary of $G_\bot$ are sums of those currents.  Therefore the potentials at the boundary of $G_\bot$, $\psi$ are given by $T \Lambda_{\gamma} \phi$.  

To get the potentials on the interior of $G_{\bot}$, recall that voltages times conductances give currents, so 
\begin{equation}
         \begin{bmatrix}
           A_\bot  &  B_\bot \\
           B_\bot^{T} &  C_\bot
         \end{bmatrix}
         \begin{bmatrix}
           \psi \\ v
         \end{bmatrix}
         = \begin{bmatrix}
           * \\ 0
         \end{bmatrix}
\end{equation}
where the first matrix is the Kirchhoff matrix of conductances of the dual graph, $\psi$ is the potential at the boundary, $v$ is the potential in the interior, * is the current on the boundary, and because $v$ is harmonic, there is 0 net current at each interior node.  This matrix equation gives an expression for $v$:
\begin{equation}
v = -C_{\bot}^{-1} B_{\bot}^T \psi
\end{equation}

\end{proof}

A possible area of further study would be to attempt to write $v$ entirely in terms of $K$, rather than using $K_\bot$.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Y-\Delta Equivalent Graphs and dual Graphs
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Y-$\Delta$ Equivalent Graphs and Dual Graphs}

The next question that arises when dealing with dual graphs, is how similar is a graph to its dual?  Specifically, when is a graph Y-$\Delta$ Equivalent to its dual?  To answer these questions, I need to use the concepts of \textit {medial graphs, circular pairs, z-sequences,} and \textit{the Cut-Point-Lemma} as defined in \cite{CM} and \cite{CIM}.  I also expand on these concepts by describing what the $z-sequence$ for a dual graph is, and defining a $rotation$.  

The medial graph $M(G)$ of a graph is a graph such that vertices of $G$ map to cells in $M(G)$.  The construction of the medial graph is discussed in chapter eight of $\cite{CM}$.  A medial graph divides the disc into regions or cells which can be colored so that a black cell shares faces with only white cells and a white cell shares faces only with black cells.  Black cells correspond to vertices in the original graph, and white cells correspond to vertices in the dual graph.  Every interior node in a medial graph has degree four.  An example of a graph and its medial graph is illustrated in figure $\ref{medialGr}$.  \\

%%%%%%%%%%%%%%%%%%%%Picture%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=6cm]{medial.eps}
\caption{A Medial Graph\label{medialGr}}
\end{center}
\end{figure}


\begin{definition}
A $\textit{circular pair}$ $(P;Q) = (p_1, ..., p_k; q_1, ..., q_k)$ is a sequence of boundary nodes such that $p_1, ..., p_k, q_1, ..., q_k$ is in counter-clockwise circular order around the disc.
\end{definition}

\begin{definition}
A $k$-$connection$ is a set of paths made of vertices and edges in $G$ such that $p_1$ is connected to $q_k$, $p_2$ is connected to $q_{k-1}$, and so forth.  Also, all of the paths must be disjoint, that is, they cannot share vertices or edges.  
\end{definition}

\begin{definition}
A graph $G$ is $critical$ if removing any edge in the graph breaks a connection.  
\end{definition}

\begin{definition}
Suppose $G$ is a critical circular planar graph with $n$ boundary nodes which is embedded in the plane so that the boundary nodes $v_1, ..., v_n$ occur in counter-clockwise order on a circle $C$ and the rest of $G$ is in the interior of $C$.  Then the medial graph $M(G)$ has $n$ geodesics each of which intersects $C$ twice.  The $n$ geodesics intersect $C$ in $2n$ distinct positions.  The $2n$ points are called position numbers and labeled $t_1,...,t_{2n}$, so that $t_1 < v_1 < t_2 < t_3 < ... < t_{2n-1} < v_n < t_{2n} < t_1$ in the circular order around $C$.  The geodesics are labeled as follows.  Let $g_1$ be the geodesic which begins at $t_1$.  The remaining geodesics are labeled $g_2, g_3, ..., g_n$ so that if $i < j$, then the first point of intersection of $g_i$ with $C$ occurs before the first point of intersection of $g_j$ with $C$ in the counter-clockwise order starting from $t_1$.  For each $i = 1, 2, ..., 2n,$ let $z_i$ be the number of the geodesic which intersects $C$ at $t_i$.  In this way we obtain a sequence $z = z_1, z_2, ..., z_{2n}$, called the $z-sequence$ for $M(G)$.  Each of the numbers from $1$ to $n$ occurs in $z$ exactly twice.  An example of a graph and its $z-sequence$ is shown in figure 5.
\end{definition}

%%%%%%%%%%%%%%%%%%%%Picture%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=6cm]{graphZseq.eps}
\caption{Graph with z-sequence 1,2,3,4,1,2,4,3 \label{Zseq}}
\end{center}
\end{figure}

\begin{definition}
Now consider the dual graph $G_{\bot}$.  If I consider the $2n$ $t_i$ positions as fixed, the boundary vertices of $G$ occur on $C$ such that $t_1 < v_1 < t_2 < t_3 < v_2 < ...$ but the boundary vertices of $G_{\bot}$ occur on $C$ such that $t_1 < t_2 < v_{\bot 1} < t_3 < t_4 < v_{\bot 2} < ...$.  Therefore in the {\textit{z-sequence of $G_\bot$ }}, let $g_{\bot 1}$ be the geodesic which begins at $t_2$, then label the remaining geodesics in the same manner as before as in figure $\ref{dZseq}$.
\end{definition} 

%%%%%%%%%%%%%%%%%%%%Picture%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\begin{center}
\includegraphics[width=6cm]{dualZseq.eps}
\caption{Dual Graph with z-sequence 1,2,3,4,1,3,2,4\label{dZseq}}
\end{center}
\end{figure}

\begin{definition}
The relabelling of the geodesics to get the $G_\bot$ $z$-sequence is called a $rotation$.  
\end{definition}

\begin{definition}
Note that since position numbers for a graph are fixed, I can define {\textit{addition on position numbers}}.  If $p$ is position number $t_i$, then $p+1$ is position number $t_{i+1}$.  Also $t_{2n+1} = t_{1}$. 
\end{definition}

With the preceding definitions, I now present some theorems.  

\begin{theorem}\label{rotation}
A connected, critical, circular planar graph $G$ and its dual $G_{\bot}$ have the same $z$-sequence (that is, a rotation preserves a $z$-sequence) if and only if the the $z$-sequence is $1, ..., n, 1, ..., n$.
\end{theorem}

\begin{proof}

Assume that a rotation preserves the $z$-sequence.  Then an actual rotation of the medial graph by one node must be able to be superimposed on the original medial graph exactly.  Then, if $p$ and $q$ are position numbers of two endpoints of the same geodesic, the $p+1$ and $q+1$ positions must also have a geodesic connecting them.  Then positions $p+2$ and $q+2$ must also have a geodesic connecting them, and so forth.  \\

%%%%%%%%%%%%%%%%%%%%%Picture%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure} [h]  
\begin{center}
\includegraphics[width=8cm]{PtoQ2.eps}
\caption{A vertex cannot be the endpoint of two different geodesics\label{PtoQ}}
\end{center}
\end{figure}

Suppose $p$ and $q$ are not $n$ positions apart.  Without loss of generality, assume that there are equal or greater than $n$ boundary nodes on the arc traversed counter-clockwise from $p$ to $q$.  Now the $2n$ position numbers must be paired so that $p$ and $q$ are two endpoints of the same geodesic, $p+1$ and $q+1$ are two endpoints of the same geodesic, $p+2$ and $q+2$ are two endpoints of the same geodesic, etc.  But then there must be a position number $x \neq q$ between $p$ and $q$ such that $x$ and $p$ are two endpoints of the same geodesic, as shown in figure $\ref{PtoQ}$.  But this is a contradiction because $p$ cannot be an endpoint of two different geodesics.  Therefore if the rotation preserves the $z$-sequence, then the two endpoints of every geodesic must be $n$ positions apart, and the $z$- sequence must be $1, ..., n, 1, ..., n$. \\

Assume now that a graph $G$ has $z$-sequence $1, ..., n, 1, ..., n$.   Then if $p$ and $q$ are two endpoints of the same geodesic, $p$ and $q$ are $n$ positions apart.  Then a rotation will preserve that $z$-sequence.   \\

\end{proof}



\begin{theorem}\label{wellC}
If a critical, connected graph's $z$-sequence is $1, ..., n, 1, ..., n$ then the graph is well-connected.
\end{theorem}

\begin{proof}
Note that if the $z$-sequence is $1, ..., n, 1, ..., n$, then there are $n$ geodesics in the medial graph and $n$ boundary nodes in the graph.  Let $\mu$ be the number $n/2$ if $n$ is even, and $(n-1)/2$ if $n$ is odd.  The largest possible circular pair $\{ p_1, ..., p_{\mu}; q_1, ..., q_{\mu} \}$ has size $\mu$.  \\

I first show that if the $z$-sequence is $1, ..., n, 1, ..., n$, then the graph has all possible $\mu$-connections.  Pick an arbitrary $\mu$-sized circular pair, $\{ p_1, ..., p_{\mu}; q_1, ..., q_{\mu} \}$.  If $n$ is even, place a cut in the white cell of the medial graph immediately before $p_1$ and place the other cut point in the white cell immediately after $p_\mu$.  If $n$ is odd, place one of the cut points in the black cell corresponding to the only boundary node not in the circular pair.  Place the other cut point on the opposite side of the circle so that each arc contains only $p$ nodes or only $q$ nodes.  The number, $b$, of whole black cells on either arc is $\mu$.  Since the $z$-sequence is $1, ..., n, 1, ..., n$, the number, $r$, of re-entrant geodesics is 0.  Then by the Cut-Point-Lemma, the maximum integer, $m$, such that there is a $k$-connection from one arc to the other is $m = b - r = \mu - 0 = \mu$.  Therefore, the graph has all possible $\mu$-connections.  \\

\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm]{induction2.eps}
\caption{Drawing a k+1 connection\label{induction}}
\end{center}
\end{figure}

Next I will show that the graph has all possible connections $( p_1, ..., p_{k}; q_1, ..., q_{k})$ when all the $p_{i}$'s are contiguous and all the $q_i$'s are also continguous.  Pick an arbitrary circular pair $( p_1, ..., p_{k}; q_1, ..., q_{k})$ where $k$ can be any integer less than $\mu$, and the $p_i$'s are contiguous and the $q_i$'s are contiguous.  Let $u$ be the set of boundary nodes between $q_k$ and $p_1$, and let $|u|$ be the number of elements in $u$.  If $|u|$ is even, place the first cut point on a white cell to divide the $u$ nodes into two equal groups.  If $|u|$ is odd, place the first cut point on a black cell corresponding to the middle $u$ node.  Place the second cut point on the opposite side of the circle so the two arcs each contain the same number of boundary nodes.  There exists a unique $\mu$-connection between the two arcs.  This connection pairs each of the nodes in $u$ with another node in $u$, and then each $p_i$ is uniquely paired with the corresponding $q_j$, so the $k$-connection joining the circular pair is embedded in the unique $\mu$-connection.  Thus there is a $k$-connection between any circular pair when all the $p_{i}$'s are contiguous and all the $q_i$'s are also continguous.  In particular, all possible 1-connections exist.\\

Finally, I will show by induction that the graph has all possible $k$-connections.  I have already shown that this statement is true when $k=1$.  Assume the statement is true for a given $k$.  Now pick an arbitrary circular pair of size $k+1$, $( p_1, ..., p_{k+1}; q_1, ..., q_{k+1})$.  Since I have already shown that all possible $\mu$-sized connections exist, look at a $\mu$-connection where $p_{k}$ is paired with $q_2$.  This connection is topologically equivalent to straight parallel, disjoint lines that divide $G$ into regions.  Call the set of these paths the ladder set.  Call the path or line between $p_k$ and $q_2$ line $H$, and say that the region $\textit{below H}$ is the region of the disc that contains $p_{k+1}$ and $q_1$.  Since I am assuming that the graph has all possible $k$-connections, look also at the $k$-connection $( p_1, ..., p_{k}; q_2, ..., q_{k+1})$.  This $k$-connection may have paths below line $H$.  Take a pair of nodes: a $p_i$, and the $q_j$ to which $p_i$ is connected.  Look at the region, $R$, in $G$ bounded by two of the parallel lines in the ladder set that are specified by the points $p_i$ and $q_j$.  Redraw the path in the $k$-connection that connects $p_i$ and $q_j$:  1) When the path lies within the region $R$, do not change it.  2) When the path leaves the region $R$, replace that part of the path with the part of the horizontal line in the ladder set.  By repeating this process for all $p_i$ and $q_j$ in the $k$-connection, I can redraw the $k$-connection in such a way that all paths in the $k$-connection are on or above line $H$, and all those paths are still disjoint, as shown in figure $\ref{induction}$.  \\

There also exists a 1-connection from $p_{k+1}$ and $q_1$.  Redraw the 1-connection in a similar manner.  Look at the region $R$, in $G$ bounded by the two parallel lines in the ladder set, one of which contains $p_{k+1}$ and one which contains $q_1$.  When the 1-connection lies within the region $R$, do not change it.  2) When the 1-connection leaves the region $R$, replace that part of the path with the part of the horizontal line in the ladder set.  Therefore there exists a 1-connection from $p_{k+1}$ to $q_1$ below line $H$.  Combine this 1-connection with the redrawn $k$-connction to get a $k+1$ connection on our arbitary circular pair.  By induction, this shows that the graph has all possible $k$-connections for any $k$.  

\end{proof}



\begin{theorem}\label{Zseq}
If a critical graph is well-connected then its z-sequence is 1, ..., n, 1, ..., n.
\end{theorem}

\begin{proof}
Well-connected means that for every circular pair $( p_1, ..., p_{k}; q_1, ..., q_{k})$, there exists a $k$-connection; in particular, all possible $\mu$-connections exist.  Pick the $\mu$-sized circular pair $( p_1, ..., p_{\mu }; q_1, ..., q_{\mu })$ such that the $p_i$'s are the first $\mu$ vertices.  Make two cuts in the circle $C$ such that all points $p_i$ are in one arc, and all the other points are in the other arc.  The maximum integer $m$ such that there is a $m$-connection from one arc to the other is $\mu$.  The number of black cells, $b$. which are entirely within the arc is also $\mu$.  Then by the Cut-Point-Lemma, the number of re-entrant geodesics $r$ is $r = b - m = \mu - \mu = 0$.  Therefore the first half of the $z$-sequence is $1, ..., n$.  By the same argument, for any two cut points which divide the number of geodesic ends evenly, the corresponding $n$ elements of the $z$-sequence must contain all the numbers from $1$ to $n$.  Therefore, the $z$-sequence is $1, ..., n, 1, ..., n$.
\end{proof}



\begin{theorem}
Given a critical, connected, circular planar graph $G$, the dual graph $G_{\bot}$ is $Y-\Delta$ equivalent to $G$ if and only if $G$ is well-connected.  
\end{theorem}

\begin{proof}
The proof is given by proving three statements:\\
1. Two graphs are $Y-\Delta$ equivalent if and only if their z-sequences are the same.\\
2. A graph and its dual have the same z-sequence if and only if the the z-sequence is 1, ..., n, 1, ..., n.\\
3. A graph is well-connected if and only if its z-sequence is 1, ..., n, 1, ..., n.\\
\\

Statement 1 is proven by Theorem 7.2 of the paper {\textit{Circular Planar Graphs and Resistor Networks}}, by E.B. Curtis, D. Ingerman, and J.A. Morrow.  Statement 2 was proven by theorem $\ref{rotation}$, and statement 3 was proven by theorems $\ref{wellC}$ and $\ref{Zseq}$.\\
\\
\end{proof}

                                                                                                                         



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Bibliography
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}

\bibitem{CM}Curtis, Edward B., and James A. Morrow.  ``Inverse Problems
for Electrical Networks.''  Series on applied mathematics -- Vol.\ 13.
World Scientific, \copyright 2000.

\bibitem{CIM}Curtis, Ingerman, and Morrow. ``Circular Planar graphs and resistor networks." Linear Algebra and its Applications 283 (1998) p.115-150

\end{thebibliography}

\end{document}