1,403 views

A vertex colouring with four colours of a graph G = (VE) is a mapping V → {RGBY }. So that any two adjacent vertices does not same colour. Consider the below graphs:

The number of vertex colouring possible with 4 colours are _________.

In the solution, they used the dearragement logic. It is well-known that inner complete graph can be colored in 24 ways but they used dearrangement for outer graph. Like if we assign Red to E then we can color A other than Red and green to G then can color D other than green, through this lets color A with Blue which is other than Red and D with also blue which is other than Green,  now this case is clearly violating graph coloring property.

How, to solve this one?

inner part you know : 4! ways

How B and D have only one choice?

If A and C are same colors (let say which is already colored by G), B has two colors (color of E and color of H) and D has three colors (color of E and color of H or color of F)

If A and C are same colors (let say which is already colored by F), B has two colors (color of E and color of H and color of G) and D has two colors (color of E and color of H)

@Anu007

if another way A =3 possible then we can choose B instance of C then 2 possible

after that we can choose C,  2 possible and last D only 1 possible color

so 3*2*2=12

12*24= 288

any wrong this method

@Bikram

by

1
1,580 views