A graph G is given by means of the adjacency matrix M:

This adjacency matrix describes a graph with 10 nodes. The element M1,2 = 1 describes an edge from node 1 to node 2 etc. By the way, this graph is supposed to be a difficult example for coloring questions, it is called Birkhoff’s Diamond.
1 Draw a sketch of this graph.
2 Try to find a coloring of this graph by hand.
3 Design a Boolean model of this problem.
4 Find a solution.
5 Is the solution a unique solution?

Transcribed Image Text:

M 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 010 0 10 10 000 10 0 01 1 0 1 0 0 0 1 1 0001011001 1 0 0 0 101000 1 0 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0,