\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{epsfig}
\setlength{\topmargin}{-.55in} \setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.1in}
\newcommand{\br}{\mathbf {R}}
\newcommand{\bq}{\mathbf {Q}}
\newcommand{\bz}{\mathbf {Z}}
\newcommand{\bn}{\mathbf {N}}
\newcommand{\z}{$\circ$}
\newcommand{\lph}{$\leftharpoondown$}
\begin{document}
\title{Early Writings on Graph Theory:\\Topological Connections}
\author{Janet Heine Barnett\footnote{Department of Mathematics and Physics;
Colorado State University - Pueblo; Pueblo, CO 81001 - 4901;
{\tt janet.barnett@colostate-pueblo.edu}.}}
\date{}
\maketitle
\subsection*{Introduction}
The earliest origins of graph theory can be found in puzzles and
game, including Euler's K\"onigsberg Bridge Problem and Hamilton's
Icosian Game. A second important branch of mathematics that grew
out of these same humble beginnings was the study of position
(``analysis situs''), known today as
\emph{topology}\footnote{According to Euler, the first person to
discuss ``analysis situs'' was the mathematician and philosopher
Gottfreid Leibniz [1646 - 1716 ]. In a 1679 letter to Christian
Huygens [1629 - 1695], Leibniz wrote:
\begin{quote}
\textsf{I am not content with algebra, in that it yields neither the shortest proofs nor the most beautiful
constructions of geometry. Consequently, in view of this, I
consider that we need yet another kind of analysis, geometric or
linear, which deals directly with position, as algebra deals with
magnitude. } \cite[p. 30]{JBBiggs}
\end{quote}
Although Leibniz himself did not appear to make contributions to the development of \emph{analysis situs}, he
did make important contributions to the development of another kind of analysis. Today, Leibniz is recognized
alongside the mathematician and physicist Isaac Newton [1642 - 1727] as an independent co-inventor of
calculus.}. In this project, we examine some important connections between algebra, topology and
graph theory that were recognized during the years from 1845 -
1930.
\vspace{3pt}
The origin of these connections lie in work done by physicist Gustav
Robert Kirchhoff [1824 - 1887] on the flow of electricity in a
network of wires. Kirchhoff showed how the current flow around a
network (which may be thought of as a graph) leads to a set of
linear equations, one for each circuit in the graph. Because these
equations are not necessarily independent, the question of how to
determine a complete set of mutually independent equations naturally
arose. Following Kirchhoff's publication of his answer to this
question in 1847, mathematicians slowly began to apply his
mathematical techniques to problems in topology. The work done by
the French mathematician Henri Poincar\'{e} [1854 - 1912] was
especially important, and laid the foundations of a new subject now
known as ``algebraic topology.''
\vspace{3pt}
This project is based on excerpts from a 1922 paper in which the American mathematician Oswald Veblen [1880 -
1960] shows how Poincar\'{e} formalized the ideas of Kirchhoff. An American mathematician born in Iowa,
Veblen's father was also a mathematician who taught mathematics and physics at the State University of Iowa. At
that time, graduate programs in mathematics were relatively young in the United States. A member of the first
generation of American mathematicians to complete their advanced work in the United States rather than Europe,
Oswald Veblen completed his
Ph.D. at the University of Chicago in 1903. He remained in Chicago for two years
before joining the mathematics faculty at Princeton. In 1930, he became the first faculty member of the newly
founded Institute for Advanced Study at Princeton.\footnote{The celebrated physicist Albert Einstein (1879 -
1955) was another early faculty member of the Institute, joining Veblen there in 1931.}
A talented fund-raiser and organizer,
Veblen also served on the Institute's Board of Trustees in its early years.
During the Nazi years, Veblen was instrumental in assisting European mathematicians to find refuge in the United
States. Although some American mathematicians, including George Birkhoff (1844 - 1944), voiced opposition to
these efforts -- fearing that talented young American mathematicians would lose academic positions to the
immigrants -- the Rockefeller Foundation and other philanthropic bodies provided financial support to these
efforts as a means of recruiting world-class mathematicians and scientists to the United States. Veblen was also
instrumental in the establishment of the American Mathematical Society's \emph{Mathematical Reviews}, a
publication aimed at providing researchers with reviews of recent mathematical papers in a timely fashion.
Founded during the late 1930's when the well-known German review journal \emph{Zentrallblatt f\"ur Mathematik
und ihre Grenzgebiete} was refusing to publish reviews written by Soviet and Jewish scholars, the
\emph{Mathematical Reviews} continues to play an important role in disseminating research results and promoting
communication within the mathematical community.
In addition to his administrative and philanthropic work, Veblen was an active researcher who made important
contributions in projective and differential geometry in addition to topology, authoring influential books in
all three areas. In this project, we examine extracts from his \emph{Analysis Situs}, the first textbook to
be written on combinatorial topology. Veblen first presented this work in a series of invited Colloquium
Lectures of the American Mathematical Society in 1916. Although he remained interested in topology afterwards,
he published little research in this area following the 1922 publication of \emph{Analysis Situs}. The extracts
we examine are taken from \cite[pp. 136 - 141]{JBBiggs}.
\bigskip
\noindent \emph{Note:} This project assumes the reader is familiar with
basic notions of graph theory, including the definition of \emph{isomorphism}
and \emph{isomorphism invariant}.
Parts of the project (clearly marked as such) also assume familiarity with the
basic linear algebra concepts of \emph{rank}, \emph{kernel} and \emph{linear independence}.
As needed, the reader should refer to a standard linear algebra textbook to review these concepts.
\bigskip
\bigskip
% Start Veblen's original text.
\textsf{\centerline{\Large{\emph{\textbf{Analysis Situs}}}}
\centerline{\large{American Mathematical Society Colloquium Lectures
1916}}
\vspace{15pt}
\centerline{Symbols for Sets of Cells}}
\begin{quote}
\textsf{
%
\begin{figure}[htb]
\centerline{\epsfig{figure=veblen_fig83.eps,width=2.5in,}} \centerline{\textsf{[FIG.\ 8.3.]}}
\end{figure}
%
\begin{description}
\item[14\hspace{11pt}] Let us denote the 0-cells of a one-dimensional complex $C_1$ by
$a_1^0, a_2^0,..., a_{\alpha_0}^0$ and the 1-cells by $a_1^1,
a_2^1,..., a_{\alpha_1}^1$.
\\
\\
Any set of 0-cells of $C_l$ may be denoted by a symbol $(x_l, x_2,
\ldots, x_{\alpha_0})$ in which $x_i = 1$ if $a_i^0$ is in the set
and $x_i = 0$ if $a_i^0$ is not in the set. Thus, for example, the
pair of points $a_1^0 \, , \, a_4^0$ in Fig.\ [8.3] is denoted by
$(1, 0, 0, 1)$. The total number of symbols $(x_l, x_2, \ldots,
x_{\alpha_0})$ is $2^{\alpha_0}$. Hence the total number of sets of
0-cells, barring the null-set, is $2^{\alpha_0}-1$. The symbol for a
null-set, $(0, 0, . . . , 0)$ will be referred to as zero and
denoted by 0. The marks 0 and 1 which appear in the symbols just
defined, may profitably be regarded as residues, modulo 2, i.e., as
symbols which may be combined algebraically according to the rules
\\
$$\begin{array}{lr}
0+0=1+1=0, & 0+1=1+0=1,\\
0 \times 0 = 0 \times 1 = 1 \times 0 = 0, & 1 \times 1 = 1
\end{array}$$
Under this convention the sum (mod.\ 2) of two symbols, or of the
two sets of points which correspond to the symbols $(x_1, x_2,
\ldots, x_{\alpha_0} )= X$ and $(y_1, y_2, \ldots, y_{\alpha_0} )=
Y$, may be defined as $(x_1 + y_1, x_2 + y_2, \ldots, x_{\alpha_0} +
y_{\alpha_0} ) = X + Y$.
\\
\\
Geometrically, $X + Y$ is the set of all points which are in X or in Y
but not in both. For example, if $X = (1, 0, 0,1)$ and $Y =
(0,1,0,1)$, $X + Y = (1,1,0,0)$; i.e., X represents $a_1^0 $ and
$a_4^0$, Y represents $a_2^0 $ and $a_4^0$, and X + Y represents
$a_1^0 $ and $a_2^0$. Since $a_4^0$ appears in both $X$ and $Y$, it
is suppressed in forming the sum, modulo 2. This type of addition
has the obvious property that if two sets contain each an even
number of 0-cells, the sum (mod.\ 2) contains an even number of
0-cells.
%
\item[15\hspace{11pt}] Any set, $S$, of 1-cells in $C_1$ may be denoted by a symbol
$(x_1, x_2, \ldots, x_{\alpha_1} )$ in which $x_i = 1$ if $a_i^1$ is
in the set and $x_i = 0$ if $a_i^1$ is not in the set. The 1-cells
in the set may be thought of as labelled with 1's and those not in
the set as labelled with 0's. The symbol is also regarded as
representing the one-dimensional complex composed of the 1-cells of
$S$ and the 0-cells which bound them. Thus, for example, in Fig.\
[8.3] the boundaries of two of the faces are $(1, 0, 1, 0, 1,0)$ and
$(1, 1,0,0,0, 1)$. The sum (mod.\ 2) of two symbols $(x_1, x_2,
\ldots, x_{\alpha_1} )$ is defined in the same way as for the case
of symbols representing 0-cells. Correspondingly if $C'_1$ and
$C''_1$ are one-dimensional complexes which have a certain number
(which may be zero) of 1-cells in common and have no other common
points except the ends of these 1-cells, the sum $C'_1 + C''_1$
(mod.\ 2) is defined as the one-dimensional complex obtained by
suppressing all I-cells common to $C'$ and $C''$ and retaining all
1-cells which appear only in $C_1'$ or in $C_1''$. For example, in
Fig.\ [8.3], the sum of the two curves represented by $(1,
0,1,0,1,0)$ and $(1, 1, 0, 0, 0, 1)$ is $(0, 1, 1, 0, 1, 1)$ which
represents the curve composed of $a_2^1, a_4^1 , a_5^1 , a_6^1$ and
their ends.
%
\end{description}}
\end{quote}
\bigskip
%Project Questions.
\begin{enumerate}
\item[1.] The following questions are based
on Section 14 of Veblen's paper, in which Veblen discusses symbols
for sets of 0 - cells.
\begin{enumerate}
\item In graph terminology, what is a `0-cell'? What is a
`1-cell'?
\item How would the set of points $\{a_1^0 , a_3^0 , a_4^0 \}$ in
Fig.\ 8.3 be represented by Veblen?
\item Identify the set of points in Fig.\ 8.3 that are
represented by the following 4-tuples:
\hspace{1in} $W = (0 , 1 , 1 , 0)$ \hspace{1in} $Z = (1 , 1 , 1 ,
1)$
\item Find $W + Z$ for $W = (0 , 1 , 1 , 0)$ and $Z = (1 , 1 , 1
, 1)$.
Identify the set of points in Fig.\ 8.3 that is represented by
$W+Z$.
\item In the last paragraph of Section 14, Veblen asserts the addition
modulo 2 has a certain `obvious property.' What property is this?
How obvious is this property? Give a formal proof of the property,
and interpret it in terms of sets of `0-cells'.
\end{enumerate}
\item[2.] The following questions are based
on Section 15 of Veblen's paper, in which Veblen discusses symbols
for sets of 1 - cells.
\vspace{3pt}
Referring to Fig.\ 8.3 in Veblen's paper, let
\hspace{1in}$M$ be the circuit defined by edges $a_1^1 , a_3^1 ,
a_4^1 , a_6^1 $
\hspace{1in}$N$ be the circuit defined by edges $a_2^1 , a_3^1 ,
a_4^1 $
\begin{enumerate}
\item How would Veblen represent $M$ and $N$ as 6 - tuples?
\item Find $M + N$ mod.\ 2, and identify the circuit
represented by this sum in Fig.\ 8.3.
\end{enumerate}
\end{enumerate}
\bigskip
\noindent In section 16 and 17 of his article, Veblen defines two important matrices associated with a graph,
denoted by him as $H_0$ and $H_1$ respectively. In section 20, he provides more detail concerning the matrix
$H_1$ for graphs that are not connected. Project questions pertaining to each of these three sections of
Veblen's paper provide additional clarification of these ideas.
%Return to Veblen
\begin{quote}
\textsf{
\begin{description}
\item[16\hspace{11pt}]
Any one-dimensional complex falls into $R_0$ sub-complexes each of
which is connected. Let us denote these sub-complexes by $C_1^1 ,
C_1^2, \ldots , C_1^{R_0}$ and let the notation be assigned in such
a way that $a_i^0$ ($i = 1, 2, . . . , m_1$) are the 0-cells of
$C_1^1$, $a_i^0$ ($i = m_1+1, m_1+2, . . . , m_2$) those of $C_1^2$,
and so on.
\\
\\
With this choice of notation, the sets of vertices of $C_1^1, C_1^2
, \ldots, C_1^{R_0}$, respectively, are represented by the symbols
$(x_1, x_2, \ldots , x_{\alpha_0})$ which constitute the rows of the
following matrix.
\\
$$
H_0=\left\|
\begin{array}{cccccccccccccc}
\overbrace{1 \, 1 \, \ldots \, 1}^{m_1} & \overbrace{0 \, 0 \, \ldots \, 0}^{m_2 - m_1} & \overbrace{0 \, 0 \, \ldots \, 0}^{\alpha_0 - m_{R_0-1}} \\
0 \, 0 \, \ldots \, 0 & 1 \, 1 \, \ldots \, 1 & 0 \, 0 \, \ldots \, 0\\
\vdots & & \vdots \\
\vdots & & \vdots \\
0 \, 0 \, \ldots \, 0 & 0 \, 0 \, \ldots \, 0 & 1 \, 1 \, \ldots \, 1 \\
\end{array}
\right\|=\|\eta_{ij}^{0}\|$$
\\
For most purposes it is sufficient to limit attention to connected
complexes. In such cases $R_0 = 1$, and $H_0$ consists of one row
all of whose elements are 1.
\end{description}}
\end{quote}
%Project Question
\begin{enumerate}
\item[3.] The following questions are based
on Section 16 of Veblen's paper, in which Veblen defines the
matrix $H_0$.
\begin{enumerate}
\item In the first paragraph of this section, Veblen assumes that
we may label the `0-cells of a one-dimensional complex' in a
particular way. What graph isomorphism invariant allows him to make
this assumption?
\item Find the matrix $H_0$ for graphs $G_1$ and $G_2$ in the
appendix. Using Veblen's notation to label the vertices and edges of each graph
so that the correspondence to the associated matrix $H_0$ is clear.
%%%%% These graphs were previously labelled $G_3$ and $G_4$; revised October 2007 %%%%%
\end{enumerate}
\end{enumerate}
\bigskip
Continuing with Section 17, we consider Veblen's initial discussion of the matrix $H_1$:
%Return to Veblen
\begin{quote}
\textsf{
\begin{description}
\item[17\hspace{11pt}]By the definition ... a 0-cell is
incident with a 1-cell if it is one of the ends of the 1-cell, and
under the same conditions the 1-cell is incident with the 0-cell.
The incidence relations between the 0-cells and the 1-cells may be
represented in a table or matrix of $\alpha_0$ rows and $\alpha_1$
columns as follows: The 0-cells of $C_1$ having been denoted by
$a_i^0$, ($i = 1, 2, . . . , \alpha_0$) and the 1-cells by $a_j^1$,
($j = 1, 2, . . . , \alpha_1$), let the element of the $i$th row and
the $j$th column of the matrix be 1 if $a_i^0$ is incident with
$a_j^1$ and let it be 0 if $a_i^0$ is not incident with $a_j^1$.
For example, the table for the linear graph of Fig.\ [8.3] formed by
the vertices and edges of a tetrahedron is as follows:
%
$$\begin{tabular}{l|cccccc}
& $\alpha_1^1 $& $\alpha_2^1 $ & $\alpha_3^1 $ & $\alpha_4^1$ & $\alpha_5^1 $ & $\alpha_6^1$ \\
\hline
$\alpha_1^0$ & 1 & 0 & 0 & 0 & 1 & 1 \\
$\alpha_2^0$ & 0 & 1 & 0 & 1 & 0 & 1 \\
$\alpha_3^0$ & 0 & 0 & 1 & 1 & 1 & 0 \\
$\alpha_4^0$ & 1 & 1 & 1 & 0 & 0 & 0 \\
\end{tabular}$$
%
In the case of the complex used ... to define a simple closed curve
the incidence matrix is
\\
$$\left\|
\begin{array}{cc}
1 & 1 \\
1 & 1 \\
\end{array}
\right\|$$
\\
%
\hspace{1in}We shall denote the element of the $i$th row and $j$th
column of the matrix of incidence relations between the 0-cells and
1-cells by $\eta_{ij}^1$ and the matrix itself by
\\
$$\|\eta_{ij}^1\|=H_1$$
\\
The $i$th row of $H_1$ is the symbol for the set of all 1-cells
incident with $a_i^0$ and the $j$th column is the symbol for the set
of all 0-cells incident with $a_j^1$.
\\
\\
\hspace{20pt}The condition which we have imposed on the graph, that
both ends of every 1-cell shall be among the $\alpha_0$ 0-cells,
implies that every column of the matrix contains exactly two l's.
Conversely, any matrix whose elements are 0's and 1's and which is
such that each column contains exactly two 1's can be regarded as
the incidence matrix of a linear graph. For to obtain such a graph
it is only necessary to take $\alpha_0$ points in a 3-space, denote
them arbitrarily by $a_l^0, a_2^0,..., a_{\alpha_0}^0$, and join the
pairs which correspond to 1's in the same column successively by
arcs not meeting the arcs previously constructed.
\end{description}}
\end{quote}
%Project Questions.
\begin{enumerate}
\item[4.] The following questions are based
on Section 17 of Veblen's paper, in which Veblen defines the incidence matrix $H_1$.
\begin{enumerate}
\item Find the incidence matrix $H_1$ for graph $G_3$ in the
appendix.
%%%%% This graph was previously labelled $G_1$; revised October 2007 %%%%%
\item Sketch and label a graph with incidence matrix
$H_1 = \left(%
\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 1 \\
\end{array}%
\right)$.
\item Give two reasons why no graph can have incidence matrix
$H_1 = \left(%
\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 & 1 \\
\end{array}%
\right)$.
\item Explain why isomorphic graphs do not necessarily
have the same incidence matrix. \\
Is there some way in which we could use incidence matrices to
determine if two graphs are isomorphic? Explain.
\end{enumerate}
\end{enumerate}
\bigskip
%Return to Veblen
In Section 20 of his article, Veblen provides a more detailed analysis of the form and properties of $H_1$ for graphs that are not
connected.
\begin{quote}
\textsf{
\begin{description}
\item[20\hspace{11pt}]Denoting the connected sub-complexes of $C_1$ by $C_1^1 ,
C_1^2, \ldots , C_1^{R_0}$ as in §16 let the notation be so assigned
that $a_1^1 , a_2^1, \ldots , a_{m_1}^1$ are the 1-cells in $C_1$,
$a_{m_1+1}^1$, $a_{m_1+2}^1$, $\ldots , a_{m_2}^1$ the 1-cells in
$C_2$; and so on. The matrix $H_1$ then must take the form
\\
$$\left\|\begin{tabular}{c|c|c|c|c}
I & 0 & 0 & 0 \\
\hline
0 & II & 0 & 0 & \\
\hline
0 & 0 & III & 0 &\\
\hline
& & & \\
\end{tabular}\right\|$$
\\
where all the non-zero elements are to be found in the matrices I,
II, III, etc., and I is the matrix of $C_1$, II of $C_2$, etc. This
is evident because no element of one of the complexes $C_1^i$ is
incident with any element of any of the others.
%
\\
\\
There are two non-zero elements in each column of $H_1$. Hence if we
add the rows corresponding to any of the blocks I, II, etc. the sum
is zero (mod.\ 2) in every column. Hence the rows of $H_1$ are
connected by $R_0$ linear relations.
%
\\
\\
Any linear combination (mod.\ 2) of the rows of $H_1$ corresponds to
adding a certain number of them together. If this gave zeros in all
the columns it would mean that there were two or no 1's in each
column of the matrix formed by the given rows, and this would mean
that any 1-cell incident with one of the 0-cells corresponding to
these rows would also be incident with another such 0-cell. These
0-cells and the 1-cells incident with them would therefore form a
sub-complex of $C_1$ which was not connected with any of the
remaining 0-cells and 1-cells of $C_1$. Hence it would consist of
one or more of the complexes $C_l^i$ ($i = 1,2, . . . , R_0$) and
the linear relations with which we started would be dependent on the
$R_0$ relations already found. Hence there are exactly $R_0$
linearly independent linear relations among the rows of $H_1$, so
that if
$\rho_1$ is the rank of $H_1$, \\
$$ \rho_1 = \alpha_0 - R_0.$$
\end{description}}
\end{quote}
\bigskip
%Project Questions.
\begin{enumerate}
\item[5.]The following questions are based
on \texttt{Section 20} of Veblen's paper, in which he discusses the matrix $H_1$ for graphs that are not
connected.
\begin{enumerate}
\item In the first paragraph of this section, Veblen asserts that the matrix $H_1$
must take the form of a block diagonal matrix. Illustrate this by finding the matrix
$H_1$ for graphs $G_1$ and $G_2$ in the appendix.
Then explain in general why this must be true.
%%%%% These graphs were previously labelled $G_3$ and $G_4$; revised October 2007 %%%%%
\item In the second paragraph of this section, Veblen asserts that
the rows of matrix $H_1$ are related by $R_0$ linear relations. What does the value $R_0$ represent? Determine the $R_0$ linear relations for the incidence matrices
$H_1$ of graphs $G_1$ and $G_2$ from part (a) above.
%%%%% These graphs were previously labelled $G_3$ and $G_4$; revised October 2007 %%%%%
Suggestions: Denote the $i^{th}$ row of $H_1$ by
$z_{i}$. You may also wish to review Section 14 of Veblen's paper in which he
explains the
notation `0' as it applies to the representation of sets of 0 - cells.
\item Verify the relationship $\rho_1 = \alpha_0 - R_0$ for the
incidence matrices of graphs $G_1$ and $G_2$.
%%%%% These graphs were previously labelled $G_3$ and $G_4$; revised October 2007 %%%%%
\vspace{3pt}
\emph{Note: You will need to know how to find the
rank of a matrix to complete this question; as required, review this concept in a linear algebra textbook. Since all sums are modulo 2, you will also need to reduce the matrices to determine their rank
by hand, rather than using the matrix utility on your calculator or
some other computing device.}
\end{enumerate}
\end{enumerate}
\bigskip
\noindent Returning to Veblen's paper, we find the introduction of the concept of a `one-dimensional circuit.'
%Back to Veblen
\begin{quote}
\textsf{\centerline{One-dimensional Circuits}
\begin{description}
\item[22\hspace{11pt}]A connected linear graph each vertex of which is an end of two and
only two 1-cells it called a one-dimensional circuit or a 1-circuit.
Any closed curve is decomposed by any finite set of points on it
into a 1-circuit. Conversely, it is easy to see that the set of all
points on a 1-circuit is a simple closed curve. It is obvious,
further, that any linear graph such that each vertex is an end of
two and only two 1-cells is either a 1-circuit or a set of
1-circuits no two of which have a point in common.
%
\\
\\
Consider a linear graph $C_1$ such that each vertex is an end of an even number of edges. Let us denote by
$2n_i$ the number of edges incident with each vertex at $a_i^0$. The edges incident with each vertex $a_i^0$
may be grouped arbitrarily in $n_i$ pairs no two of which have an edge in common; let these pairs of edges be
called the pairs associated with the vertex $a_i^0$. Let $C'_1$ be a graph coincident with $C_1$ in such a way
that (1) there is one and only one point of $C'_1$ on each point of $C_1$ which is not a vertex and (2) there
are $n_i$ vertices of $C'_1$ on each vertex $a_i^0$ of $C_1$ each of these vertices of $C'_1$ being incident
only with the two edges of $C'_1$ which coincide with a pair associated with at $a_i^0$.
%
\\
\\
The linear graph $C'_1$ has just two edges incident with each of its
vertices and therefore consists of a number of 1-circuits. Each of
these 1-circuits is coincident with a 1-circuit of $C_1$, and no two
of the 1-circuits of $C_1$ thus determined have a 1-cell in common.
Hence $C_1$ consists of a number of 1-circuits which have only a
finite number of 0-cells in common.
%
\\
\\
It is obvious that a linear graph composed of a number of closed curves having only a finite number of points in
common has an even number of 1-cells incident with each vertex. Hence a \emph{necessary and sufficient condition
that $C_1$ consist of a number of 1-circuits having only 0-cells in common is that each 0-cell of $C_1$ be
incident with an even number of 1-cells}. A set of 1-circuits having only 0-cells in common will be referred to
briefly as a set of 1-circuits.
\end{description}}
\end{quote}
%Project questions
\bigskip
\begin{enumerate}
\item[6.] The following questions are based
on Section 22, in which Veblen discusses
one-dimensional
circuits.
\begin{enumerate}
\item First paragraph: Note that Veblen is
now only interested in connected graphs. According to his
definition of `1-circuit', can a 1-circuit repeat edges? vertices?
\item Second paragraph: Veblen outlines a method
for constructing a new graph $C'_1$ from a given linear graph $C_1$.
\begin{enumerate}
\item What conditions on the graph $C_1$ are required for this
construction?
\item The resulting graph $C'_1$ will depend on how we pair up
the edges at each vertex. Illustrate this fact using graph $G_4$
from the appendix. That is, apply Veblen's construction method \emph{twice} to graph
$G_4$, using different pairings of edges each time.
%%%%% This graph was previously labelled $G_2$; revised October 2007 %%%%%
\end{enumerate}
\item Third paragraph: Veblen claims that each 1-circuit of the graph $C'_1$ constructed by this method will
be coincident with a 1-circuit of the original graph $C_1$.
Use graph $G_5$ from the appendix to show that this is not
the case for any arbitrary pairing of edges in the original graph.
That is, find a pairing of the four edges at vertex $D$ of graph $G_5$ which gives us a
1-circuit of the graph $C'_1$ that is not coincident with a 1-circuit of the graph $C'_1$.
%%%%% This graph was added to the appendix in October 2007 revision. %%%%%
\item In the final paragraph of Section 22, Veblen states the
conclusion of this section in the form of a `necessary and
sufficient' statement. To what (familiar) theorem from graph theory
is this conclusion related? Explain, and comment on Veblen's proof (especially in light of question 5c
above).
\end{enumerate}
\end{enumerate}
%Back to Veblen
\bigskip
\noindent In Section 24 of \emph{Analysis Situs}, Veblen introduced an algebraic representation of
one-dimensional circuits.
\begin{quote}
\textsf{
\begin{description}
\item[24\hspace{11pt}]
Let us now inquire under what circumstances a symbol $(x_1, x_2,
\ldots, x_{\alpha_1})$ for a one-dimensional complex contained in
$C_1$ will represent a 1-circuit or a system of 1-circuits. Consider
the sum
\\
$$ \eta_{i1}^1x_1 + \eta_{i2}^1x_2 + \ldots + \eta_{i\alpha_1}^1x_{\alpha_1}$$
%
where the coefficients $\eta_{ij}^1$ are the elements of the $i$th
row of $H_1$. Each term $\eta_{ij}^1x_j$ of this sum is 0 if $a_j^1$
is not in the set of 1-cells represented by $(x_1, x_2, \ldots,
x_{\alpha_1})$ because in this case $x_j = 0$; it is also zero if
$a_j^1$ is not incident with $a_i^0$ because $\eta_{ij}^1=0$ in
case. The term $\eta_{ij}^1 x_j=1$ if $a_j^1$ is incident with
$a_i^0$ and in the set represented by $(x_1, x_2, \ldots,
x_{\alpha_1})$ because in this case $\eta_{ij}^1= 1$ and $x_j = 1$.
Hence there are as many non-zero terms in the sum as there are
1-cells represented by $(x_1, x_2, \ldots, x_{\alpha_1})$ which are
incident with $a_i^0$. Hence by $\S$22 the required condition is
that the number of non-zero terms in the sum must be even. In other
words if the $x$'s and $\eta_{ij}^1$'s are reduced modulo 2 as
explained in \S14 we must have
%
$$ (H_1) \hspace{20pt}
\sum_{i=1}^{\alpha_1}\eta_{ij}^1 x_j = 0 \hspace{20pt} (i = 1,
2,\ldots, \alpha_0)$$
%
if and only if $(x_1, x_2, \ldots, x_{\alpha_1})$ represents a
1-circuit or set of 1-circuits. The matrix of this set of equations
(or congruences, mod.\ 2) is $H_1$.
\end{description}}
\end{quote}
\bigskip
%Project Questions
\begin{enumerate}
\item[7.] Note that, in the algebraic
representation of one-dimensional circuits discussed in Section 24,
the number of non-zero terms in the sum $\eta_{i1}^1 x_1 +
\eta_{i2}^1 x_2 + \ldots \eta_{i\alpha_1}^1 x_{\alpha_1}$
corresponds to the degree of the vertex $a_i^0$.
\begin{enumerate}
\item Veblen's conclusion in the penultimate sentence of Section 24 could be re-stated in terms of solutions to the
matrix-vector equation $H_1\overrightarrow{v}=\overrightarrow{0}$,
where $H_1$ is the incidence matrix of the graph. Complete the
following example to illustrate this conclusion:
Let $H_1$ be the incidence matrix for graph $G_3$ from the appendix. (See part a of question 4 above.)
Let $\overrightarrow{X} = (1,0,1,1,0)$ and
$\overrightarrow{Y} = (1,0,0,1,1)$.
Determine the matrix-vector products (modulo 2)
$H_1\overrightarrow{X}$ and $H_1\overrightarrow{Y}$.
Use these results to determine whether
(i) $\overrightarrow{X}$ represents a set of 1-circuits in the graph
$G_3$; and (ii) $\overrightarrow{Y}$ represents a set of 1-circuits
in the graph $G_3$. Explain.
%%%%% This graph was previously labelled $G_1$; revised October 2007 %%%%%
\item What advantage might there be in representing graphs and
circuits in terms of matrices and linear equations?
\end{enumerate}
\end{enumerate}
\bigskip
\noindent In the final excerpt from Veblen's paper below, a
connection is made between the matrix $H_1$ and the problem of
determining whether there exists a complete set of 1-circuits that
will generate all possible 1-circuits for a given graph.
%Back to Veblen
\begin{quote}
\textsf{
\begin{description}
\item[25\hspace{11pt}]
If the rank of the matrix $H_1$ of the equations ($H_1$) be $\rho_1$ the theory of linear homogeneous equations
(congruences, mod.\ 2) tells us that there is a set of $\alpha_1 - \rho_1$ linearly independent solutions of
($H_1$) upon which all other solutions are linearly dependent. This means geometrically that \emph{there exists
a set of $\alpha_1 - \rho_1$ 1-circuits or systems of 1-circuits from which all others can be obtained by
repeated applications of the operation of adding (mod.\ 2) described in \S14}. We shall call this a complete set
of 1-circuits or systems of 1-circuits.
\end{description}}
\end{quote}
\bigskip
% Back to project questions
\begin{enumerate}
\item[8.] The following questions are based
primarily on Section 25, in which Veblen discusses how to use the
matrix $H_1$ to determine if there is a complete set of 1-circuits
that will generate all possible 1-circuits for a given graph.
\emph{Note: You will need to know about null space, basis sets and rank to complete this question; as required,
review this concept in a linear algebra textbook.}
\begin{enumerate}
\item Explain Veblen's conclusion in terms of null space of the
matrix $H_1$. You may find it helpful to review section 24 of Veblen's paper, and
project question 7 above.
\item Consider the incidence matrix $H_1$ for graph $G_6$ in the appendix.
%%%%% This graph was previously labelled $G_5$; revised October 2007 %%%%%
\begin{itemize}
\item Find a basis for the null space of that matrix, again using modulo 2 sums.
\item Use your null-space basis to identify a complete system of
1-circuits for this graph.
\item Write the circuit $C = ( 0 , 0 , 1 , 1 , 1 , 0 , 1 )$
as the sum of circuits in your complete system of
1-circuits for this graph.
\end{itemize}
\end{enumerate}
\end{enumerate}
\section*{Notes to the Instructor}
This project was developed for use in a beginning-level discrete mathematics course; it could also be used in
a more advanced level discrete mathematics course. Familiarity with basic notions of graph theory, including
the definition of \emph{isomorphism} and \emph{isomorphism invariant}, is assumed. Parts of the project (clearly
marked as such) also assume familiarity with the basic linear algebra concepts of \emph{rank}, \emph{kernel} and
\emph{linear independence}. The instructor may either omit these questions or refer students to a standard
linear algebra textbook as needed for review. In view of the more advanced nature of this project, small group
work is recommended for its use within a beginning level course. Although the project could be assigned
independently, assigning it following completion of one or both of the projects ``Early Writings on Graph
Theory: Hamiltonian Circuits and The Icosian Game'' and ``Early Writings on Graph Theory: Topological
Connections'' is also recommended for beginning level courses; both projects appear in the current volume. Use
of color pencils or markers will be helpful in answering Question 6.
\begin{thebibliography}{99}
\bibitem{JBBiggs} Biggs, N., Lloyd, E., Wilson, R.,
\emph{Graph Theory: 1736--1936}, Clarendon Press, Oxford, 1976.
\bibitem{JBJames} James, I., {\em Remarkable Mathematicians: From Euler
to von Neumann}, Cambridge University Press, Cambridge, 2002.
\bibitem{JBKatz} Katz, V., {\em A History of Mathematics: An
Introduction}, Second Edition, Addison-Wesley, New York, 1998.
\bibitem{JBVeblen} Veblen, O., ``An Application of Modular Equations in
Analysis Situs,'' {\em Ann. of Math.}, {\bf 14} (1912-13), 42--46.
\end{thebibliography}
\newpage
\centerline{{\bf APPENDIX: Graphs for Veblen Graph Theory Project}}
\vspace{40pt}
\begin{figure}[htb] \epsfig{figure=graph_G1.eps,
height=2.5in, width=2.5in} \hfill
\epsfig{figure=graph_G2.eps, height=2.5in, width=2.5in}\\
\\
Graph $G_1$\hfill Graph $G_2$\end{figure}
\vspace{40pt}
\begin{figure}[htb] \epsfig{figure=graph_G3.eps, height=3in, width=3in} \\
\\
Graph $G_3$
\end{figure}
\newpage
\begin{figure}[htb] \epsfig{figure=graph_G4.eps, height=2.5in, width=2.5in} \hfill
\epsfig{figure=graph_G5.eps,height=2.5in, width=2.5in}\\
\\
Graph $G_4$\hfill Graph $G_5$\end{figure}
\vspace{40pt}
\begin{figure}[htb]
\epsfig{figure=graph_G6.eps, height=2.5in,
width=2.4in}\\
\\
Graph $G_6$
\end{figure}
\end{document}