TOC 1.3

1.3. Graphs

An undirected graph or simply a graph is a set of points with lines connecting some points. The points are called nodes or vertices. The lines are called edges.

Example 1.8.

The number of edges at a particular vertex is the degree of the vertex. In Figure 1.1, degree of 1 is 3. No more than one edge is allowed between any two vertices. We label the vertices for convenience, and call the graph as labeled graph. Figure 1.1. Examples of undirected graphs An induced subgraph H of a graph G is a graph with nodes of H being a subset of the nodes of G, and edges of H being the edges of G on the corresponding nodes. A path in a graph is a sequence of nodes connected by edges. A simple path is a path that does not repeat any node. A graph is connected if any two nodes have a path between them. A path is a cycle if it starts and ends in the same node. A simple cycle is one that does not repeat any node except the first and the last. A tree graph is a connected graph that has no simple cycle. The nodes of degree 1 in a tree are called the leaves of the tree. A directed graph has directed lines between the nodes. The number of arrows pointing from a particular node is the outdegree of that node and the number of arrows to a particular node is the indegree.

Example 1.9.

In the following directed graph (Figure 1.2) the indegree of node labeled 2 is 3 and its outdegree is 1. Figure 1.2. An example of a directed graph

Definition 1.2 An undirected graph is connected if every pair of vertices is connected by a path. A path in a graph is a contiguous sequence of its vertices. In any graph G, a path forms a cycle if its starting vertex and end vertex are same. A connected, acyclic, undirected graph is a tree.

Example 1.10.

Consider the following graphs: Graphs (i) and (ii) are connected. 1 2 3 4 6 is a path in Graph (i) Graph (i) contains a cycle 1 2 3 4 5 1. Graph (ii) is a tree. The following are the observations about a tree. Let G = (V, E) be an undirected graph. Then the following statements are equivalent. G is a tree. Any two vertices in G are connected by a unique simple path. G is connected, but if any edge is removed from E, the resulting graph is disconnected. G is connected and |E| = |V| − 1. G is acyclic and |E| = |V| − 1. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle. All the above properties can be proved; and this is left as an exercise.

Definition 1.3 A rooted tree is a tree in which one of the vertices is distinguished from others. Such a vertex is called the root of the tree.

It can also be looked at as a directed graph, where only one node has indegree 0 (root). All other nodes have indegree 1. If the outdegree is 0, the node is a leaf.