Exercise 5.3 Graph Coloring

Question

Hallo,

The task is as follows,

Create a Boolean formula that can be fulfilled if and only if the above graph can be colored with three colors so that adjacent nodes do not have the same color.

Use the variables ai, bi, ci for i ∈ {1,2,3,4,5} to represent the color of a node. The variables ai or bi or ci apply precisely when the node i is colored with color a or b or c.

Exactly one color must be assigned to each node.

Incidentally, I thought a total of 6 options for 3 colors colored in such graph.

IF I only pay attention to the node, I get 3 implications for each node, then a total of 15 implications.

(a1-> !a2& !a3)& (a2-> !a1& !a3&!a4)&(a3->!a1& !a2& !a4& !a5)&(a4->!a2& !a3& !a5)&(a5->!a3& !a4)&(b1-> !b2& !b3)& (b2-> !b1& !b3&!b4)&(b3->!b1& !b2& !b4& !b5)&(b4->!b2& !b3& !b5)&(b5->!b3& !b4)&(c1-> !c2& !c3)& (c2-> !c1& !c3&!c4)&(c3->!c1& !c2& !c4& !c5)&(c4->!c2& !c3& !c5)&(c5->!c3& !c4)

it is clear that the following formula is wrong, and connected with OR also wrong,

I tried to formulate a formula out of 6 possibilities.

((a1->!a2& !a3)&(b2-> !b1& !b3&!b4)&(c3->!c1& !c2& !c4& !c5)&(a4->!a2& !a3& !a5)&(b5->!b3& !b4))|

((a1-> !a2& !a3)& (c2-> !c1& !c3&!c4)&(b3->!b1& !b2& !b4& !b5)&(a4->!a2& !a3& !a5)&(c5->!c3& !c4))|

((b1->!b2& !b3)&(a2-> !a1& !a3&!a4)&(c3->!c1& !c2& !c4& !c5)&(b4->!b2& !b3& !b5)&(a5->!a3& !a4))|

((b1-> !b2& !b3)& (c2-> !c1& !c3&!c4)&(a3->!a1& !a2& !a4& !a5)&(b4->!b2& !b3& !b5)&(c5->!c3& !c4))|

((c1-> !c2& !c3)&(a2-> !a1& !a3&!a4)&(b3->!b1& !b2& !b4& !b5)&(c4->!c2& !c3& !c5)&(a5->!a3& !a4))|

((c1-> !c2& !c3)&(b2-> !b1& !b3&!b4)&(a3->!a1& !a2& !a4& !a5)&(c4->!c2& !c3& !c5)&(b5->!b3& !b4))

everyone is wrong, where should I continue to work？

How should I think of this task?

Thanks for your help in regard.

Answer 1

I think you are trying to encode a specific colouring directly into a formula. That is not the goal here. Instead we want a formula such that every satisfying assignment of that formula corresponds to a valid colouring and vice versa.

In order to successfully colour a graph we need to satisfy the following constraints:

1. Each node gets exactly one colour
2. Adjacent nodes get different colours

Try to break these constraints down into smaller chunks, translate each to a formula and combine them with conjunctions.

---

For example if we have a node 1 and colours a b c we have the variables a1 b1 c1. The formula

(a1 | b1 | c1)

Enforces that at least one of a1 b1 c1 must be true, meaning 1 gets at least one colour. The formulas

(a1 -> !b1 & !c1) &
(b1 -> !a1 & !c1) &
(c1 -> !a1 & !b1)   

mean "If one of a1 b1 c1 is true, then the other two must be false", meaning 1 gets at most one colour.

Now try to combine them and think which of the above constraints (1. or 2.) this is. For the other constraint you will have to consider the graph's structure (try adding some constraints for each edge).

Comments

I thought about, when we checked a node  "If one of a1 a2 a3 is true, then the other two must be false",these three formulas are actually supposed to be connected with AND, otherwise a state is wrong.
If we look at the simple model: coloring 2 colors (1 2) in a knot  (a) , we limit that this knot is colored, then we only really need an additional restriction, then this knot will only.
(a1 | a2 )&(a1 -> !a2 )

then we go back to their example. This sentence corresponds to the formula
"If one of a1 a2 a3 is true, then the other two must be false"
(a1 | a2 | a3)&(a1 -> !a2 & !a3)&(a2 -> !a1 & !a3)
is it right？

---

Yes that is correct. You can drop the last constraint here, but it is also ok if you add it.

---

the first knot should then be connected to the second knot.
the statement is so, Adjacent nodes get different colors,
a simple model: one knot (a) should color with one of the 3 colors (1,2,3). and another knot (b) also with the same restriction of a. In addition, a and b are connected, and then there is an additional restriction , they should be of uneven color.
(a1->! b1) & (a2 ->! b2) & (a3 ->! b3)
I have already checked with the tool, connection of the 2 nodes is so.
(a1 | a2 | a3) & (a1 ->! a2 &! a3) & (a2 ->! a1 &! a3)) & ((b1 | b2 | b3) & (b1 ->! b2 &! b3) & (b2 ->! b1 &! b3)) & (a1 ->! b1) & (a2 ->! b2) & (a3 ->! b3)
but with 3 knots is still wrong, not just 3 knots, connect with AND.
How to connect 3 nodes？
for example, node a and node (b, c) connect in triangles, then each node should only be colored one color, and a is not equal to b and c.
(a1 ->! b1 &! c1)
(a2 ->! b2 &! c2)
(a3 ->! b3 &! c3)
consider b, then
(b2 ->! a2 &! c2)
..... three more formulas,
and c
...... 3 more formula.
 should end up assembling these 9 formulas directly under the 3 node connection？

---

I just noticed that we used numbers for colours and letters for nodes. The exercise wants it the other way around, so I updated my answer accordingly.

> "they should be of uneven color"
Where did you get this from? That is not part of the exercise and also doesn't make much sense. If the nodes can't use odd colours then there are simply less colours to choose from. It's the same as using half the number of colours without that restriction.

The formula you made for two nodes looks good already. If you have more nodes and more edges, just generate the constraints in the same way and combine them all with a conjunction. The ones you write there look correct, but there are still some missing.

And don't forget that we swapped the letters and numbers.

---

yes i know, to fit your example, i intentionally return the name of the color and node.As well as spoken at the very beginning, when knots 1,2,3 are determined, 4,5 also becomes clear, in which case there is actually only 6 options for coloring.