Graphs -- basic definitions

1.0 In the near vicinity of mathematics, a graph or graph-like object is a binary relation on a set N (namely a subset of the set of all ordered pairs of elements of N).

Traditionally within "mathematics-proper" a graph is a system (that is, a "multinary relation") <N,L> in which N is a set, N={n₁, n₂, n₃, ...n_p} and L is a subset of  L the set of all pairs of distinct elements of N. (That is, L = N x N - {(n_i,n_i)} . ) Elements of N are called nodes; elements of L are called lines. The number of nodes as defined above is often denoted by the letter p, sometimes called the size of the graph.

G1: a graph,
consisting of four nodes
and six lines.

1.1 If there is a line between two nodes n_i and n_j , we say the nodes are adjacent or connected and write n_i | n_j . Two graphs are considered isomorphic if there is a labelling of the nodes which preserves adjacency. (That is, if G₁=<N₁,L₁> and G₂=<N₁,L₂> implies L₁=L₂.)

G2: a graph.
G2 is isomorphic to the graph G1. All nodes 
in both graphs are adjacent to one another.

1.2 Adjacency may be demonstrated by constructing the adjacency matrix of a graph: a p by p matrix, in which the entry (i,j) = 1 if n_i | n_j and (i,j)=0 otherwise.

Demonstrating the isomorphism of G1 and G2 
through their shared adjacency matrix.

1.3 In traditional graph theory, all lines are bidirectional; that is if n_i | n_j then so is n_j | n_i . A graph-like object in which the lines are sometimes unidirectional is called a directed graph. Lines in a directed graph are often called arcs.

A directed graph: an arrow leading 
from a to b is read as a is connected to b

1.4 Also, in traditional graph theory, two nodes are, quite simply, either connected or not. That is, the number of lines between two nodes is at most one. A graph-like object that allows more than one line between two nodes is called a multigraph.

A multigraph: in which pairs of
nodes may be multiply connected

1.5 A graph-like object in which a node is allowed to be connected to itself, is called a pseudograph.

In the above pseudograph, one 
node has an line leading to itself.

1.6 If each pair of successive nodes, (n_i, n_i+1), in a sequence of distinct nodes (n₁, n₂, n₃, ...n_k) is connected, then the sequence  is called a path. The number of lines in a path is called the length of the path. The length of the shortest path between two nodes is called the distance between the nodes.

G3: A connected graph.
The sequences (1,2,3,4,5) and (1,2a,3,4,5) represent two 
different paths from node 1 to node 5. The sequence 
(2,3,4,5) and represents a shortest path of length 3 from 
node 2 to node 5. The sequence (2,1,2a,3,4,5) is a path 
of length 5 from node 2 to node 5. The path (1,2,3,2a)
is a cycle, since 1 is connected to 2a.

1.7 A path  (n₁, n₂, n₃, ...n_k) in which  n₁ | n_k (namely, the start node of the path is also connected to the end node) is called a cycle. (See explanation following G3.)

1.8 A graph in which for each pair of nodes, n_i and n_j, there exists a path from node i to node j, is called connected. A graph in which, for some pair of nodes, n_q and n_w , there is no path, is called disconnected.

A disconnected graph.

1.9 A graph which has no cycles is called a tree.

A tree.
Start at any node and begin walking along a path. Observe that for
each successive step on the path, distance from the start node increases.
This is not always true in a graph with cycles.

2.0 The degree of a node refers to the number of nodes it is adjacent to.

2.1 A graph in which each node has the same degree is called a regular graph.

A regular graph of degree three,
also known as a "cubic" graph. Click
to see its construction from a non-
regular graph.

References:  The above treatment is largely (as per memory) consistent (in denotation rather than in connotation) with Graph Theory by Frank Harary, publ. Addison Wesley, 1970. (Dr. Harary, in our discussions across various parts of the continent, seemed reluctant to talk about the "periphery of mathematics," and would, I think, welcome distance from such whimsy.)

It is also vaguely derived from my memory of Graph Coloring by Humans and Machines: a polynomial complete problem solving task by D.P. Dailey, doctoral dissertation, University of Colorado, 1978.

Copyright notice: So long as the above presentation does not infringe on the references cited (and it doesn't, at least if the laws of the universe have been properly constructed), it is intended by its author to belong to the public domain. David Dailey,   January 2001 .