Introduction to Graph Theory

These and many other practical problems comprise graph theory which is an important mathematical tool in a wide variety of subjects, ranging from computer science and geography to sociology and architecture, and from genetics and linguistics to operational research and chemistry.

A simple graph G consists of a non-empty finite set V of elements named vertices (singular: vertex) and a set E of distinct unordered pairs of distinct elements of V named edges. We call V the vertex-set and E the edge-set of G.

Vertices that are joined by edges are called adjacent vertices. For instance, in the graph given in Figure 7.1, u and v are adjacent vertices while u and w are nonadjacent

All vertices that are adjacent to vertex v are called the neighbours of v. For example, it is easy to see that in the graph given in Figure 7.1 the neighbours of x are w, y, and z.

The degree of a vertex v is the number of edges incident with v. The notation d(v) denotes the degree of vertex v. For instance, in the graph given in Figure 7.3, d(a)=3, d(b)=2, d d (c)=2, d(d)=3, and d(e)=2. Since d(a)=3, we interpret that team a has played 3 games.

Perhaps the oldest result in graph theory was discovered by the famous mathematician Euler. 

If all of the vertices in a graph are adjacent to each other, then the graph is called a complete graph. The complete graph on n vertices is denoted by Kn. For n=1, 2, 3, 4, 5, and 6 complete graphs Kn are shown in Figure 7.6

A walk in a graph is a sequence of vertices v0, v1, v2,…,vk such that v0 is adjacent to v1, which is adjacent to v2, which is adjacent to v3 and so on. That is any two consecutive vertices in the sequence must be connected by an edge. We simply denote it by v0 v1 v2 ... vk. We call v0 the initial vertex and vk the final vertex of the walk, and express a walk from v0 to vk. A walk is closed if its endpoints (initial and final vertices) are the same

An Eulerian walk is a walk that goes through every edge exactly once (the walk may or may not be closed). For instance, in the graph of Figure 7.8 a b c d e b d a f e a is an (closed) Eulerian walk.

We first introduce planar graphs, which are graphs that can be drawn without any crossings on the plane. Such a drawing is called a plane diagram. For example, complete graph K4 is a planar graph. Three diagrams of K4 are shown in Figure 7.14. The second and third diagrams are plane diagrams, while the first is not

Now we state Euler’s formula which tells us that whatever plane diagram of a planar graph we take, the number of regions is always the same and is given by a simple formula. Let G be a connected planar graph with n vertices and m edges, and let f be the number of regions in any plane diagram of G.

A bipartite graph is a graph whose vertices can be separated into two sets A and B in a such a way that every edge in the graph has one endpoint in each set. Figure 7.19 is an example of bipartite graph, while Figure 7.20 is not.

A complete bipartite graph is a bipartite graph in which each vertex in A is joined to each vertex in B by an edge. We denote the complete bipartite graph by the symbol K r,s, where r and s are the number of vertices in A and B respectively. K2,3, K3,3 and K4,3 are shown in Figure 7.21. Basically K r,s has r+s vertices and rs edges. The graph shown in Figure 7.19 is complete bipartite graph K4,4.

When Euler was trying to find his formula, he was studying polyhedra (solids bounded by plane polygons) like cube, pyramids and prisms. For some polyhedra, number of faces, edges and vertices are presented in Table 7.22.

A simple graph G is k-colourable if we can assign one of k different colours to each vertex so that adjacent vertices have different colours. Another way of stating this is that each edge has two endpoints of different colours. If graph G is k-colourable but is not (k-1)-colourable, we say that the chromatic number of G is k, and write χ(G)=k. For instance, Figure 24 shows a graph G for which χ(G)=3. Hence, it is k-colourable when k≥3.

A tree is a graph which is connected and contains no cycles (see Figure 7.28).

A weighted graph is a graph G, in which each edge e has been assigned a nonnegative real number w(e), called the weight of e. The weight of a graph is simply defined to be the sum of the weights of its edges. For example, the weight of the graph shown in Figure 7.32 is 1+2+3+4+5+6+7+8+9+10+11=66.

If G is a connected graph then, (if there exist) we can choose a cycle and remove any one of its edges, and the resulting graph remains connected. We repeat this operation with one of the remaining cycles, proceeding until there is no cycle left. The obtained graph is a tree containing all the vertices of G. It is called a spanning tree of G. A graph and three of its spanning trees are illustrated in Figure 7.33.

Hence, we seek a spanning tree of a graph G, so that its weight is minimum among all spanning trees of G. Such a spanning tree is termed minimum spanning tree. The problem of finding the minimum spanning tree is called the minimum spanning tree problem.

Kruskal’s Algorithm: For a connected weighted graph G, a spanning tree T of G is constructed as follows: For the first edge e1 of T, we select any edge of G of minimum weight and for the second edge e2 of T, we select any remaining edge of G of minimum weight. For the third edge e3 of T, we choose any remaining edge of G of minimum weight that does not produce a cycle with the previously selected edges. We continue in this way until a spanning tree is produced. Figure 7.34 shows how a spanning tree of a connected weighted graph is constructed using Kruskal’s Algorithm.