(Back to MM322 homepage)

A graph comprises:

Alternatively, to avoid having to define  ¶,  we could define the edges by their endpoints so that E is a list (possibly with repeats) of one or two element sets of vertices. This is Wilson’s approach, although he calls  E  a ‘family’; mathematically,  E  is a bag. The disadvantage of this approach is that it does not allow us to identify different edges joining the same vertices.

If  ¶(e) = {v, w}  then  e  joins  v  and  w;  if  ¶(e) = {v}  then e is a loop.

If  ¶(e1) = ¶(e2)  then  e1  and  e2  are multiple edges.

If  ¶(e) = {v1, v2}  then  v1  and  v2  are incident with  e,  and  e is incident with  v1  and  v2.

The vertices  v1  and  v2  are adjacent if there exists an edge e such that  ¶(e) = {v1, v2}.

An isolated vertex is a vertex which has no edges incident with it.

A simple graph is a graph which has no loops or multiple edges.

The degree of a vertex is the number of (distinct) edges incident with it. A loop contribute 2 to the degree of the vertex with which it is incident.

The degree sequence of a graph  G  is the sequence of its vertex degrees, written in non-decreasing order.

The adjacency matrix of a graph with vertex set  V = {v1, v2, …, vn}  is an n ´ n matrix  A = (aij)  where  aij  is the number of edges which join  vi  and  vj.

A graph is regular of degree  r  if every vertex has degree  r.

A graph is complete if it has no loops and every pair of distinct vertices is joined by a unique edge. The complete graph with n vertices is denoted  Kn.

A graph  G  is bipartite if the vertex set  V  is the union of two disjoint, non-empty sets  V1  and  V2  such that each edge of  G  joins and edge of  V1  and an element of  V2.  (The sets  V1  and  V2  form a partition of the vertex set  V.)

A complete bipartite graph is a bipartite graph in which each vertex in  V1  is joined to each vertex in  V2  by a unique edge. If  V1  has  r  vertices and  V2  has  s  vertices (symbolically,  #(V1) = r  and  #(V2) = s) then the corresponding complete bipartite graph is denoted  Kr,s.

Let  G  and  H  be graphs. An isomorphism  G ® H  is a bijection  q: V(G) ® V(H)  such that, for all  v1, v2 Î V(G),  the number of edges joining  v1  and  v2  is the same as the number of edges joining  q(v1)  and  q(v2)  in  H.  If there exists an isomorphism  G  ®  H  then  G  and  H  are isomorphic, written  G @ H.

Let  G  and  H  be two graphs.

To show that  G  is isomorphic to  H,  we must find an appropriate isomorphism  G ® H.

To show that  G  is not isomorphic to  H,  we must find a graph-theoretic property which one graph has but the other does not.

A graph  H  is a subgraph of a graph  G   if  V(H) Í V(G)  and every edge of  H   is also an edge of  H.  We write   H £ G   to mean  H   is a subgraph of  G.

A walk of length n is a finite sequence of edges  e1, e2, …, en  where, for each  i = 1, 2, …, n,  ¶(ei) = {vi–1, vi}  (where  vi–1 = vi  is allowed); in other words, each successive pair of edges in the sequence is adjacent to a common vertex.

The associated vertex sequence is  v0, v1, v2, …, vn;  the vertex  v0  is the initial vertex and the vertex  vn  is the final vertex of the walk.

A trail is a walk in which all the edges are distinct.

A closed walk or trail starts and ends at the same vertex; that is  v0 = vn.

A path is a trail in which all vertices are distinct (except, possibly, the first and last vertex).

A cycle (or circuit) is a closed path.

A graph is connected if, for each pair of distinct vertices, there is a path from one to the other; a graph which is not connected is disconnected.

A graph splits into a number of connecetd pieces called components; a connected graph has one component. Formally, a component of  G  is a maximal connected subgraph of  G.