GRAPH THEORY - TERMINOLOGY 4

 CONNECTED GRAPHS, DISCONNECTED GRAPHS, AND COMPONENTS

A graph G is said to be connected if there is at least one path between every pair of vertices in G.

Connected graph

 Otherwise, G is disconnected. 

A null graph of more than one vertex is disconnected

A disconnected graph consists of two or more connected graphs. Each of these connected subgraphs is called a component.

Theorem 1: A graph G is disconnected if and only if its vertex set V can be partitioned into two nonempty, disjoint subsets V1 and V2 such that there exists no edge in G whose one end vertex is in subset V1 and the other in subset V2

Proof

Suppose that such a partitioning exists. Consider two arbitrary vertices a and b of G, such that a ∈ V1 and b ∈ V2 . No path can exist between vertices a and b; otherwise, there would be at least one edge whose one end vertex would be in V1 and the other in V2 . Hence, if a partition exists, G is not connected.

Conversely, let G be a disconnected graph. Consider a vertex a in G. Let V1 be the set of all vertices that are joined by paths to a. Since G is disconnected, V1 does not include all vertices of G. The remaining vertices will form a (nonempty) set V2 . No vertex in V1 is joined to any in V2 by an edge. Hence the partition.

Theorem 2: If a graph (connected or disconnected) has exactly two vertices of odd degree, there must be a path joining these two vertices.

Proof

Let G be a graph with all even vertices† except vertices v1 and v2 , which are odd. From Theorem 1, which holds for every graph and therefore for every component of a disconnected graph, no graph can have an odd number of odd vertices. Therefore, in graph G, v1 and v2 must belong to the same component, and hence must have a path between them. 

Theorem 3: A simple graph (i.e., a graph without parallel edges or self-loops) with n vertices and k components can have at most (n − k)(n − k + l)/2 edges.

Resource: Graph Theory with Applications to Engineering & Computer Science NARSINGH DEO