MathDB

Each vertex of a finite graph can be coloured either black or white. Initially all vertices are black. We are allowed to pick a vertex

P

and change the colour of

P

and all of its neighbours. Is it possible to change the colour of every vertex from black to white by a sequence of operations of this type? Note: A finite graph consists of a finite set of vertices and a finite set of edges between vertices. If there is an edge between vertex

A

and vertex

B,

then

A

and

B

are neighbours of each other.

Problem Statement