prove that if the graph e leq v23 G is 3colorable then Solut

prove that if the graph e leq v^{2}/3 G is 3-colorable then

Solution

We need to prove the result using induction taking the base cases and then proving it for higher values

Let number of vertices be 1, then there is no edges hence the graph can be 3 colorable

Let the number of vertices be 2, then there exists e <= 4/3 which means edges must be 1, since there are two connected vertices so only 2 colors are enought to color the graph

Let the number of vertices be 3, then the graph can contain maximum of 3 edges which means all the three vertices are connected to each other

i.e. v1 connected to v2, v2 connected to v3 and v3 connected to v1

so let v1 be red, v2 be green and v3 be blue (3-colorable)

let us assume the graph of n vertices with n^2/3 edges is 3 colorable

then we need to prove for graph n+1 vertices

number of edges in (n+1) vertices graph = (n+1)^2/3 = (n^2 + 2n + 1 )/3 = (n^2 + 2n + 1)/3

hence adding the extra vertex can connected to all the (n-1) points hence 2n/3 is less than (n-1) therefore for a 3 colorable graph the number of edges must be less than vertices^2/3