in Graph Theory
1,403 views
3 votes
3 votes

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?

in Graph Theory
1.4k views

4 Comments

inner part you know : 4! ways

0
0
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)
0
0

@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

0
0

1 Answer

0 votes
0 votes

I do'nt think 216 is the answer please have a look at this link https://math.stackexchange.com/questions/2496188/number-of-ways-to-color-this-graph