Graph-theory glossary for
Freshman Seminar 23j: Chess and Mathematics
(Fall 2004)
Graph theory, like chess, has an extensive collection of technical terminology. As with the chess glossary, this glossary is limited to basic terms of graph theory that we'll need for our seminar and whose meaning may not be obvious.
adjacency matrix (n.; the plural is ``adjacency matrices''): A table of 0's and 1's that encodes the structure of a graph. The rows and columns are labeled by the vertices; the entry in row r and column c is 1 if and only if (r,c) is an edge of the graph. Thus an adjacency matrix is a square table, which is diagonally symmetrical unless the graph is directed. For example,
0 1 0 0 1 
1 0 1 0 0 
0 1 0 1 0 
0 0 1 0 1 
1 0 0 1 0 
is an adjacency matrix of a pentagon, and
0 0 0 0 1 
1 0 0 0 0 
0 1 0 0 0 
0 0 1 0 0 
0 0 0 1 0 
is an adjacency matrix of a directed pentagon. (I write ``an adjacency matrix'' rather than ``the adjacency matrix'' because the table depends on how the vertices are ordered; for instance
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 
is also an adjacency matrix of a directed pentagon. What's the total number of different adjacency matrices of this directed graph?)

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 V1, V2, such that every edge of the graph connects a V1 vertex to a V2 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 V1 vertex is connected with every V2 vertex. Such a graph is sometimes called Kn1,n2, where n1,n2 are the numbers of vertices in the two parts V1,V2. For example, a square is a complete bipartite graph (namely K2,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 Kn, where n is the number of vertices. For example, a triangle is a complete graph (namely K3), 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 Kn, 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.