Chapter B, Problem 1P

Program Plan Intro

To show that any tree is 2-colorable.

Explanation of Solution

Given Information:

A of an undirected graph is a function such that for every edge

Explanation:

There are no loops in tree, if a color (0) is given to a node, then all its neighbors should be colored with a different color say color (1). Now color the neighbors of all these neighbors with color (0). In this way keep coloring alternating colors until the whole tree is colored. Since there are no loops no node will be visited and thus colored twice. In the end any path in the tree has vertices with alternating colors.

Program Plan Intro

To show that the following are equivalent:

1. G is bipartite.
2. G is 2-colorable.
3. G has no cycles of odd length.

Explanation of Solution

A bipartite graph has two sets of vertices which has equal number of vertices in those two sets. So, if the given graph G is bipartite that means it will be 2 colorable because one set of vertices can be colored with one color say color (0) and another set of vertices can be colored with another set of vertices say color (1).

The following figure shows the bipartite graph with chromatic number

  

Also, it can be seen that it has no cycles of odd length from the above figure of bipartite graph.

So, on the basis of above illustration- the following points can be made-

1. G is bipartite.
2. G is 2-colorable.
3. G has no cycles of odd length.

Program Plan Intro

To prove that a Graph can be colored with colors where is the maximum degree of any vertex in graph.

Explanation of Solution

Greedy coloring procedure requires us to number the colorsthat are used. So, each time a new color is introduced it is numbered.

Greedy coloring algorithm:

If the maximum degree vertex of a graph has degree d, let this vertex be v.

Color v with color 1.

Since all the adjacent vertices of 'v' have to be colored with a color other than color of 'v', let us assume that all the adjacent vertices are colored with different colors.

As number of neighbors is d, hence number of additional colors required is d. So, maximum d+1 colors are needed.

This is the maximum number of colors needed because in no case there will be more than d+1 colorsas the maximum degree is d. (All the neighbors and other nodes of graph have degree <= d)

Proof by mathematical induction:

Base case: A graph with just 1 vertex has maximum degree 0 and needs only 1 color. It is 1-colorable.

Inductive hypothesis: It can be assumed that any graph which has = k vertices and maximum vertex degree = d can be colored with d+1 colors.

Inductive Step: Now suppose there is a graph G with k+1 vertices and maximum degree d. Remove a vertex v (and all its edges) from G to create a smaller graph G'.

The maximum degree of G' is not greater than d, because removing a vertex from G' won't increase its degree. So, by the inductive hypothesis, G' can be colored with d + 1 colors. The neighbors of v are only using d of the available colors because v has maximum d neighbors, leaving a spare color that can be assigned to v.

Therefore, the coloring of G is an extension of coloring of G'. Hence, G can be colored with d+1 colors. G is (d+1)-colorable.

Program Plan Intro

To show that a graph G can be colored with if it has edges.

Explanation of Solution

Run the above greedy algorithm when a coloris used for the first time, to color a vetexmark the edges joining to vertices already coloured which is atleast

Every marked edge is marked only once during the process and at least edges will be marked when number of colors are used. So if number of colors are present, then number of edges will be colored.