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={n1, n2, n3,} and L is a subset of  L the set of all pairs of distinct elements of N. (That is, L = N x N - {(ni,ni)} . ) Elements of N are called nodes; elements of L are called lines (or, sometimes, edges). The number of nodes as defined above is often denoted by the letter p, sometimes called the size of the graph.

g1.GIF (1941 bytes)
G1: a graph,
consisting of four nodes and six lines.

1.1 If there is a line between two nodes ni and nj , we say the nodes are adjacent or connected and write ni— nj . Two graphs are considered isomorphic if there is a labeling of the nodes which preserves adjacency. (That is, if G1=<N1,L1> and G2=<N1,L2> implies L1=L2.)

g2.GIF (1906 bytes)
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 ni — nj and (i,j)=0 otherwise.

  n1 n2 n3 n4
n1 0 1 1 1
n2 1 0 1 1
n3 1 1 0 1
n4 1 1 1 0
Demonstrating the isomorphism of G1 and G2 
through their shared adjacency matrix.

1.2.5 Given a graph G = <N,L>, a graph G' = <N', L'> is called a subgraph of G, if N' is a subset of N and L' is a subset of L.

1.3 In traditional graph theory, all lines are bidirectional; that is if ni—nj then so is nj— ni . 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.

g4.GIF (1504 bytes)
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.

g5.GIF (1576 bytes)
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.

g6.GIF (1447 bytes)
In the above pseudograph, one 
node has an line leading to itself.

1.6 If each pair of successive nodes, (ni, ni+1), in a sequence of distinct nodes (n1, n2, n3, ...nk) is connected, then the sequence  is called a path. Such a path is sometimes called a path from its start node, n1 to its end node nk.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.

g8.GIF (1875 bytes)
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  (n1, n2, n3, ...nk) in which  n1 — nk (namely, the start node of the path is also connected to the end node) is called a cycle. (See explanation following G3.)  If a graph consists only of a single path on k nodes, we may refer to that graph as Pk .

1.7.5 Cn is defined as the graph consisting solely of a cycle on n nodes. C3, is hence, a triangle.

1.8 A graph in which for each pair of nodes, ni and nj, there exists a path from node i to node j, is called connected. A graph in which, for some pair of nodes, nq and nw , there is no path, is called disconnected.

g7.GIF (2048 bytes)
A disconnected graph consisting of two components (one C3 and the other C4).

1.8.2 A node m is called reachable from another node n, if there is a path from n to m.

1.8.5 A connected subgraph consisting of the union of all nodes reachable from a given node is called a component.

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

g9.GIF (1751 bytes)
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.

h3.gif (1168 bytes)
A regular graph of degree three,
also known as a "cubic" graph. Click
to see its construction from a non-
regular graph.


2.2 A graph is called complete if every node in the graph is connected to every other node.

2.3 The complete graph on n nodes is referred to as Kn .

Since the number of pairs of n objects is nC2 = n(n-1)/2, K3 has 3 lines, K5 has 10 lines, and K6 has 15 lines.

2.4 A graph is called planar if it can be drawn in the plane with no crossing lines.

Note: the graph K4 is planar (as shown in the figure for G1 earlier in this document) even though the following depiction of it is not:
K4That is, this is a nonplanar representation of the planar graph K4.

The graph K5 is nonplanar (a result due to Kuratowski), implying that Kn is non planar for all n>4. This follows, trivially, since if K5 cannot be embedded in the plane without crossing lines, it is obvious that any larger graph which contains it is also not planar.

2.5 A graph is called bipartite if its nodes may be divided into two subsets (known as partitions) A and B in which n in A and n—p means that p must belong to B. That is all lines lead between the two sets, with no lines between any nodes within a set.

Example: C6 is bipartite. We can see this by labeling the nodes sequentially around the cycle from 1 to 6. Odd numbered nodes are never connected to one another, nor are even numbered nodes, implying that it is bipartite.

2.5.5 A complete bipartite graph is a bipartite graph in which each pair of nodes in different partitions is connected. If there are n nodes in one partition and m in the other, then we will write this complete bipartite graph as Km,n.  The number of lines in Km,n is mn.

Example:  C4 can also be written as C2,2 .

Another result do to Kuratowski is that K3,3 is nonplanar.

2.6 A graph is called k-colorable if its nodes may be divided into  k sets, where no two nodes in the same set are connected to one another. The smallest number x such that a graph is x-colorable, is called the chromatic number of the graph.  When a graph is k-colored, the k sets are called colors. Trivially,  a graph is 2-colorable graph if and only if it is bipartite.

Example: C4 is 4-colorable (assigning a separate color to each node), but it is also 2-colorable. It is not 1-colorable, so its chromatic number is 2.

2.7 A graph is called hamiltonian if there is a cycle that includes every node of the graph. Such a cycle is called a hamiltonian cycle.

2.8 A graph is called eulerian if there is a walk that traverses each edge exactly once. The walk is called an eulierian trail.

2.9 If a connected graph has a node, the removal of which (including the removal of all its edges) results in a graph with more than one component, then that node is called a cutpoint.

2.9.5 If a connected graph has a line, the removal of which results in a graph with more than one component, then that line is called a bridge.

3.1 Take a graph G=<N,L>. Produce a new graph H has follows.. Let H=<N, L'> where L' consists of all pairs of nodes not in L. Then H is called the complement of G.

3.2 A maximal clique of a graph is a largest complete subgraph.

3.3 The node independence number of a graph is the size of the largest set of nodes, no two of which are adjacent.

3.4 The size of the smallest set of nodes such that all nodes in the graph are adjacent to at least one of the members of that set is called its domination number. Such a set is called a dominating set.

3.5 Given two graphs G1=<P,L1> and G2=<Q,L2>, we may construct the product of those graphs G1 x G2 as follows:

Let Q={q1,q2,q3,...qQ}. Make |P| copies of the graph G2 .  . Label the nodes in the kth copy Gk as  Qk ={qk1,qk2,qk3,...qkQ}

Let qki be adacent to qmj if and only if pk is adacent to pm in G1 .

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 have, I think, welcomed 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 .