Freshman Seminar 23j: Chess and Mathematics

(Fall 2004)

1 0 1 0 0

0 1 0 1 0

0 0 1 0 1

1 0 0 1 0

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

**
adjacent
**
(adj.): Two vertices v,v' of a graph are said to be ``adjacent''
[to each other] if {v,v'} is an edge of the graph.

**
bipartite
**
(adj.): A graph is bipartite if its set of vertices can be split
into two parts V_{1}, V_{2}, such that every edge
of the graph connects a V_{1} vertex to a V_{2} vertex.
For example, a hexagon is bipartite but a pentagon is not.
More generally, we'll see that a graph is bipartite if and only if
all cycles in the graph have even length. In particular,
all trees (q.v.) are bipartite: a tree has no cycles at all,
so *a fortiori* no odd cycles.

**
clique
**
(n.): A subset S of the vertices of a graph such that
all pairs of vertices in S are adjacent.

**
coclique (co-clique)
**
(n.): A subset S of the vertices of a graph such that
no two vertices in S are adjacent. A coclique in a graph
is a clique in its complementary graph (q.v.).

**
complement, complementary graph
**
(n.): for any graph G, the complementary graph of G
(a.k.a. the complement of G) is the graph with the same vertices
as the vertices of G but with all the edges not in G.
For instance, the complementary graph of a pentagon is a pentagram.
If G' is this complementary graph then
G is in turn the complement of G'.

**
complete bipartite graph
**
(n.): A bipartite graph in which every V_{1} vertex
is connected with every V_{2} vertex.
Such a graph is sometimes called
K_{n1,n2},
where n_{1},n_{2} are the numbers of vertices
in the two parts V_{1},V_{2}.
For example, a square is a complete bipartite graph
(namely K_{2,2} -- right?), but no other polygon is.

**
complete graph
**
(n.): A graph in which every pair of vertices is adjacent.
Such a graph is sometimes called K_{n},
where n is the number of vertices.
For example, a triangle is a complete graph (namely K_{3}),
but no other polygon is.

**
connected
**
(adj.): A graph is connected if every pair of vertices is connected
by some path. The Bishop graph of an 8*8 chessboard is not connected;
all other pieces yield connected graphs.

**
degree
**
(n.): the degree of a vertex of a graph is the number of other vertices
that it is adjacent to. For instance, in a polygon all vertices
have degree 2; in the Petersen graph, all vertices have degree 3;
and in the complete graph K_{n}, all vertices have degree n-1.
Thus all three of these graphs are regular (q.v.).
The sum of the degrees of all vertices in a graph G
equals twice the number of edges of G (why?);
in particular, this sum must be an even number.

**
diameter
**
(n.): The diameter of a graph is the maximal distance between
any two points on the graph. If the graph is not connected,
its diameter is infinite.

**
distance
**
(n.): The distance between two vertices v,v' (often denoted
``d(v,v')'') is the length of the shortest path connecting them.
Thus:

@ d(v,v')=0 if and only if v=v';

@ d(v,v')=1 if and only if v and v' are adjacent;

@ d(v,v')=2 if and only if v and v' are neither the same nor adjacent
but have a common neighbor;

@ ``etc.''.

Note that this definition does in fact satisfy the axioms
(required properties) required for a ``distance'':

i) nonnegativity: for all vertices v and v', the distance d(v,v')
is either positive or zero, and zero if and only if v=v';

ii) symmetry: d(v,v')=d(v',v) for all v and v';

iii) triangle inequality: for all v,v',v'' the distance d(v,v'')
is no larger than d(v,v')+d(v',v'') [why?].

If the graph is not connected, there are some vertices v,v'
not connected by any path. In that case we say that
d(v,v') = +.
The above axioms still hold with natural interpretations
of inequalities and arithmetic involving +.

**
edge
**
(n.): See **graph**.

**
Euler(ian) circuit,
Euler(ian) path
**
(n.): An Euler path (a.k.a. Eulerian path) in a graph G
is a path that traverses each edge of G exactly once.
If the initial and final vertices are the same then the path
is an Euler(ian) circuit. Named in honor of Euler,
who proved that: G has an Euler path if and only the number
of vertices of odd degree is 0 or 2; it has an Euler circuit
if and only if all vertices have even degree; and in this case
all Euler paths are circuits. (There cannot be just one odd degree
because the sum of all the degrees is even.)
Look up ``bridges of Königsberg'' on the Web
for the charming history of this problem.

**
girth
**
(n.): The girth of a graph is the length of the shortest cycle(s)
in the graph. If the graph has no cycles, its girth is infinite.

**
graph
**
(n.): A mathematical structure
consisting of a (usually finite) set of ``vertices''
together with a set of ``edges'' which are pairs of vertices
(usually regarded as ``connections'' between pairs of vertices).
Unless otherwise specified, we do not allow loops (edges connecting
a vertex to itself), nor multiple edges joining the same two vertices.
If the graph is directed, its edges are ordered pairs of vertices;
usually our graphs are undirected, so the edges are unordered pairs.

**
Hamiltonian circuit,
Hamiltonian path
**
(n.): A Hamiltonian path in a graph G
is a path that goes through each vertex of G once.
If the initial and final vertices are adjacent
then the path can be completed to a Hamiltonian circuit.
Knight's tours and closed Knight's tours are examples
of Hamiltonian paths and Hamiltonian circuits respectively.
Unlike their Eulerian cousins, Hamiltonian paths and circuits
can be hard to find, or even to tell whether they exist on a given
graph G: it is known that finding a Hamiltonian path or circuit
on a general graph G is an ``NP-complete'' problem.

**
isomorphic
**
(adj.),
**
isomorphism
**
(n.):
These are central notions not just in graph theory but in all of
modern mathematics. Two mathematical objects, call them A and B,
are *isomorphic* if they have the same structure; that is,
if there is a 1:1 map from A to B that preserves all of the structure
relevant to these objects. Such a map is an *isomorphism*.
When A,B are graphs, an isomorphism is a bijection from the vertices
of A to the vertices of B such that any two vertices of A are adjacent
if and only if their images in B are adjacent. For example,
the pentagon and pentagram are isomorphic as graphs; one isomorphism
takes vertices 1,2,3,4,5 to 1,3,5,2,4. If A and B are isomorphic
then they have identical graph-theoretical properties; for instance,
since the pentagon is regular of degree 2, with diameter 2 and girth 5,
the same is automatically true also of the pentagram once we know
that the two graphs are isomorphic.

**
regular
**
(adj.):
A graph is regular if all its vertices have the same degree (q.v.).
The Rook graph of an 8*8 chessboard is regular of degree 14 --
that is, a Rook on an empty board can go to 14 other squares,
regardless of which square it stands on.
None of the other chess pieces yields a regular graph.

**
**

**
tree
**
(n.): A connected graph with no cycles.
Exercise: Prove that every tree has exactly one fewer edge
than its number of vertices.

**
vertex
**
(n.): See **graph**.
The plural is **vertices**.

**
**