0 votes 0 votes Graph Theory discrete-mathematics graph-theory engineering-mathematics chromatic-numbers counting + – screddy1313 asked Jan 25, 2019 • edited Jan 25, 2019 by screddy1313 screddy1313 453 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Satbir commented Jan 25, 2019 reply Follow Share we need 3 colours and we have 8 vertices so C(8,3) since graph has odd cycle. 0 votes 0 votes screddy1313 commented Jan 25, 2019 reply Follow Share Graph is four colorable....but the ques is how many different type of labellings?? 0 votes 0 votes Satbir commented Jan 25, 2019 reply Follow Share then it should be C(8,4) 0 votes 0 votes screddy1313 commented Jan 25, 2019 reply Follow Share In C(8,4) also it has to follow coloring property i.e no two adjacent vertices should have same color No I think there will be more than C(8,4) 0 votes 0 votes Satbir commented Jan 25, 2019 reply Follow Share this property will be covered when we are selecting chromatic number. 0 votes 0 votes Akash purbia commented Feb 12, 2019 reply Follow Share here chromatic no. is always is equal to 4 because in this graph there is a complete graph K4 .and we know that a complete graph is n- colorable.and if we select any vertex randomly then we can say that it is 4- colorable. total no. of different labeling = 1.selection of 1 vertex at a time out of 8 vertex =$\binom{8}{1}$=8. 2.four colors can be arranged in 4! ways =24. so, total no. different labeling = 8*24=192. am i correct? 0 votes 0 votes Please log in or register to add a comment.