colouring

We consider graphs with vertices colored black or white. "Switching" a vertex means: coloring it black if it was formerly white, and coloring it white if it was formerly black.

Consider a finite graph with all vertices colored white. Now, we can do the following operation: Switch a vertex and simultaneously switch all of its neighbours (i. e. all vertices connected to this vertex by an edge). Can we, just by performing this operation several times, obtain a graph with all vertices colored black?

[It is assumed that our graph has no loops (a loop means an edge connecting one vertex with itself) and no multiple edges (a multiple edge means a pair of vertices connected by more than one edge).] S

3 Answers

1
Shreyan ·

yes, we can.....(tried out with diff combinations....and besides, i had a game almost exactly like this.....)

39
Dr.House ·

assume that the hypothesis is valid for n-1 and A is n*n matrice .

suppress the i th row and ith column,we get n-1*n-1 matrice with same property,then according to the hypothesis there exist some column such that their sum mod 2 equal n-1 dimention vector (1,...,1),now if we add the similar columns of A we get n dimention vector s.t all its component equals 1 just maybe ith component is'nt,if there exists i such that the number of 1 in its row is odd we are done otherwise for any1≤i≤ n according to above we get v(i)=(1,1,...,0,1,1,...,1) assume that n is even then we have $v(1)+...+v(n)\equiv (1,...,1) means that if we add the column which is in relation to v(i) we get (1,1,...) but in this summand maybe some column is used more than 1 ,so if some column is used even times we can omit it and or we can consider column in parityso we can get (1,1,..1) and for n=2k+1

39
Dr.House ·

hope u can understand it

Your Answer

Close [X]