**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_{1},
n_{2}, n_{3}, ...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 (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: 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
labeling of the nodes which preserves adjacency. (That is, if G_{1}=<N_{1},L_{1}>
and G_{2}=<N_{1},L_{2}> implies L_{1}=L_{2}.)

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.

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 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 asa 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_{1}, n_{2}, n_{3},
...n_{k}) is connected, then the sequence is called a **path**.
Such a path is sometimes called a path **from** its start node, n_{1}**to** its end node n** _{k}**.The number of lines in a path is called the

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 ashortestpath 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_{1}, n_{2}, n_{3}, ...n_{k})
in which n_{1} — n_{k} (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 P_{k} .

**1.7.5 C _{n}** is defined as the graph consisting solely of a
cycle on n nodes. C

**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 consisting of two components (one Cand the other C_{3})._{4}

**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**.

**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.

Since the number of pairs
of n objects is nC2 = n(n-1)/2, K_{3} has 3 lines, K_{5
}has 10 lines, and K_{6} has 15 lines.

Note: the graph K

_{4}is planar (as shown in the figure for G1 earlier in this document) even though the following depiction of it is not:

That is, this is a nonplanar representation of the planar graph K_{4}.

The graph K_{5}is nonplanar (a result due to Kuratowski), implying that K_{n}is non planar for all n>4. This follows, trivially, since if K_{5}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: C

_{6}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 K_{m,n}. The number of lines in K_{m,n} is mn.

Example: C

_{4}can also be written as C_{2,2}.Another result do to Kuratowski is that K

_{3,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 G_{1}=<P,L_{1}> and G_{2}=<Q,L_{2}>, we may construct the product of those graphs G_{1} x G_{2} as follows:

Let q

__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 .