Question

The graph M. (r 2) is obtained from the cycle graph Czr by adding extra edges joining each pair of opposite vertices. Show that: (i) (ii) (iii) My is bipartite when r is odd, X(M) = 3 when r is even and r #2, x(M2) = 4.

Answer 1

I have in detail explained for you all the steps of the proof and the motivation behind framing such a proof. Kindly go through. This is a very constructive proof. There may exist some other proofs also. But since I love constructing proofs and is easily understandable for a student what is the idea behind, I have done in this way. Also I have shown in the proof by two examples how we could colour and have generalised it.

(i) Mai 20 r-odal. r+ 4 9 r+3 raz Aye MP a ter DI bo Here we see that i and rri are joined Since r is odd consider the bipartition X= {1,3,5,7,...v} and Y= {2,4,6,8,...}. An edge in G joins precisely an even labelled vertes and an odd labelled vertex. So It is clear that My is bipartite for or an odd number . (i) Let rta be an even number. Consider My. The cycle Con has chromatic number a. So our My must have X atleast a. But here we see if we are assign in a least possible way with a colours, even numbers will have Red (some colour) and odd numbers will have (Blue) (some colour). Scanned with - CamScanner Ben YE

Since ris even, rtl is odd and we have an edge joining and ry. Hence they cannot be given same colour (say Bree). So we need atleast & colours to colour the graph Now we will show that we can colour My (neven) with 3 colours : First let us understand with some examples: MA: y to - IR - 5G GR ® y What is the idea is : we give R to l, G to 2 and 27(8). Also to (r+1) 5. Now give (8) 1) 4 , (+2) 6 the colour red (R). Now 7 (x+(0-1)) another colour y and make an ladjustment I that give 4 the colour Y and then s the colour red (R). [The colour of 4]. as where will is the colour obesite to colour of 2 . CamScanner

М. : *+(-1) - 12 G IR på G IR SR - ₂. ! r+(x-2). 106/ +(2-3) sady Ky+ 3 XG şr erta 7+1 n ce een As earlicar colour I with R, aranda with G. Also r+1=7 with G. Now colour &, r+2 with R. Continue like this. Since r is even we obtain a stage where .. (the vertex labeled 8+ N) where, rtv will be adjacent with a greens vertex, a red vertex and we will have to colour +7 and 7 So here we make an adjustment that we give + the colour y Cyellow), r+r the colour (yellow) Y and give õ the previous colour opposite (x - 1). Here Red. CS UU e e E CS Scanned with CamScanner

ener ven rem EN . 1. This idea gives us a general colouring. Give the odd vertices 1,3,...,k where k <3 the colour red R. The even vertices 2,4,... m where mar the colour G. So V+ 1; dit, 3 ...,r+k will be given G and &+2, 8+4,..., &rm will be given R. Now givers r+r the colour Y and give 7 - LG if k is adjacent to & R if m is adjacent to a Also replace the colour of 7+1 to Y. Cyellow). So we coloured the graph using 3 colours and bence XCM) = 3 , when roto2 is an even number. (vii) Me: X (M₂) = 4 is clear since vertices 1, 2, 3, 4 are adjacent to 72G each other and so they must have 4 different colours. my ca 3 B Scanned with CamScanner