Question

Graph 2
Prove the following statements using one example for each (consider n > 5).
(a) A graph G is bipartite if and only if it has no odd cycles.

(b) The number of edges in a bipartite graph with n vertices is at most (n2 /2).

(c) Given any two vertices u and v of a graph G, every u–v walk contains a u–v path.

(d) A simple graph with n vertices and k components can have at most (n-k).(n-k+1)/2 edges.

Answer 1

(a). Let G(V, E) be an undirected bipartite graph,

V(G) = X U Y ; X $\bigcap$ Y $\notequal$ = null;

Consider G has an odd cycle C with length n.

C = (v1, v2, v3, ... vn, v1)   

Consider v1 $\epsilon$ X then the following shoul be true since G is bipartite.

v2 $\epsilon$ Y, v3 $\epsilon$ X, v4 $\epsilon$ Y, ....... and so on vn $\epsilon$ X since n is an odd number.

=> v1, v3, v5, ... vn   $\epsilon$ X (odd nodes)

v2, v4, v6, ....    $\epsilon$ Y (even nodes)

But both v1 and vn are under set X which contradicts the assumption of bipartite.

Hence, proved that a graph is bipartite if and only if it has no odd cycles.

(b). For a bipartite graph, there will not be an edge between any nodes in the same subset.

Consider a graph G(V, E) with n vertices as a bipartite. Let X and Y be the two partitioned subsets and x and y are the corresponding numbers of vertices in each set.

Then the maximum no. of edges in bipartite = x * y

This product is maximum when x = y

hence max no. of edges in bipartite = x * x

= (n/2) * (n/2) [since n = x + y and x =y , n = 2 * x => x = n/2]

= n2 / 4 > n2/2

Hence proved

(c). A path is a tree with two nodes of degree 1 and all other nodes of degree 2. A walk is a sequence of v1, e1, v2, e2, ... vk, ek. Hence if u and v are two vertices in a walk, then there are edges between each node in the walk u-v; Hence there is a tree connecting u and v. Thence there should be a path u-v in a u-v walk.

(d). Can be solved in two cases.

If the number of components, k > 1 then the maximum number of edges achieve only when only one of the component has more than one vertex. Let that component be X.

Let k be the number of components,

then, max no. of vertices in the component X = n - k + 1

then max no. of edges in this largest component X = (n-k+1)((n-k+1) - 1)/2 [max no. of edges in a graph = n*(n-1)/2]

= (n-k+1)(n-k)/2

If the number of components = 1 then the component is the graph itself. In this case also

max no. of edges is (n-k)(n-k+1)/ 2 = n(n-1)/2, whis is also true.

Hence proved