2025
Discrete Mathematics
Lec #3.1
Satisfiability Problems
Reference Book: Discrete Mathematics and Its Applications (7th edition)
By
Kenneth H. Rosen
National University of Sciences & Technology (NUST) 1
SAT Problem: Suduko Puzzle
2
SAT Problem: Suduko Puzzle
3
SAT Problem: Suduko Puzzle
[Link]
4
SAT Problem: Suduko Puzzle
5
SAT Problem: 3-colouring Problem
• Given a graph 𝐺 = 𝑉 𝐸 and 𝑘colors, can we assign a color to each vertex such that:
• Every vertex has exactly one color.
• Adjacent vertices have different colors.
• Encoding into SAT
• Suppose the graph has 𝑛 vertices: 𝑣1 , 𝑣2 , … , 𝑣𝑛 . We introduce Boolean variables:
• 𝑥𝑖,𝑐 = True if vertex 𝑣𝑖 has color 𝑐
• where 𝑖 = 1, … , 𝑛 and 𝑐 = 1, … , 𝑘 .
6
SAT Proble: 3-colouring Problem
• Each vertex has at least one color
• For each vertex 𝑣𝑖 :
• 𝑥𝑖,1 ∨ 𝑥𝑖,2 ∨ ⋯ ∨ 𝑥𝑖,𝑘
• Each vertex has at most one color
• For each vertex 𝑣𝑖 and for all pairs of colors 𝑐 ≠ 𝑑 :
¬𝑥𝑖,𝑐 ∨ ¬𝑥𝑖,𝑑
• Adjacent vertices have different colors
• For each edge 𝑣𝑖 𝑣𝑗 ∈ 𝐸 and for each color 𝑐 :
• ¬𝑥𝑖,𝑐 ∨ ¬𝑥𝑗,𝑐
7
SAT Proble: 3-colouring Problem
A colouring of a graph is an assignment of colours to its vertices such that every two
adjacent vertices are coloured differently.
8
4-colouring Problem
The problem of determining the minimum number (or a reasonable number) of time slots
needed to schedule all the courses subject to restrictions is a graph coloring problem. Figure
1 illustrates a simple timetabling problem instance in which we have five courses to be
scheduled: Physics, Calculus, Electronics, Microprocessors, and Operating Systems.
9
5-colouring Problem
10
5-colouring Problem
11
5-colouring Problem
12
5-colouring Problem
13
5-colouring Problem
14
5-colouring Problem
15
5-colouring Problem
16
5-colouring Problem
17
5-colouring Problem
18
Applications
United States of America ( states are presented into 4 different colors)
19
Applications
World Map using 7 different colors)
20
chromatic number
The smallest number of colors needed to color a graph G is called its
chromatic number
21
Graph Coloring Problem
Example: Triangle Graph (3-cycle)
Graph: 3 vertices 𝑣1 , 𝑣2 , 𝑣3 ,edges 1 2 , 2 3 , 3 1 .
Colors: 𝑘 = 3(Red, Green, Blue).
Variables: 𝑥1,𝑅 , 𝑥1,𝐺 , 𝑥1,𝐵 , 𝑥2,𝑅 , … , 𝑥3,𝐵 .
Constraints:
• Each vertex has at least one color (3 clauses).
• Each vertex has at most one color.
• Adjacent vertices must differ (triangle requires all 3 different colors).
• If satisfiable then the graph is 3-colorable.
22
Graph Coloring Problem
Example: Given a graph G with vertices V={1,2,3,4}
and edges E={(1,2),(2,3),(3,4),(4,1)}
• write down the SAT clauses to test if the graph is 3-colorable.
• For the graph above, show whether the SAT formula is satisfiable.
We use Boolean variables 𝑥𝑣,𝑐 meaning “vertex 𝑣 has color 𝑐”, where 𝑣 ∈ 1 2 3 4 and
𝑐∈ 123
)1.) CNF clauses
(A) Each vertex has at least one color (one clause per vertex)
1. 𝑥1,1 ∨ 𝑥1,2 ∨ 𝑥1,3
2. 𝑥2,1 ∨ 𝑥2,2 ∨ 𝑥2,3
3. 𝑥3,1 ∨ 𝑥3,2 ∨ 𝑥3,3
4. 𝑥4,1 ∨ 𝑥4,2 ∨ 𝑥4,3
23
Graph Coloring Problem
B) Each vertex has at most one color (pairwise exclusion for each vertex)
For vertex 1:
For vertex 3:
5. ¬𝑥1,1 ∨ ¬𝑥1,2
6. ¬𝑥1,1 ∨ ¬𝑥1,3 11. ¬𝑥3,1 ∨ ¬𝑥3,2
7. . ¬𝑥1,2 ∨ ¬𝑥1,3 .12¬𝑥3,1 ∨ ¬𝑥3,3
.13¬𝑥3,2 ∨ ¬𝑥3,3
For vertex 2:
For vertex 4:
8. ¬𝑥2,1 ∨ ¬𝑥2,2
.9 ¬𝑥2,1 ∨ ¬𝑥2,3 14. ¬𝑥4,1 ∨ ¬𝑥4,2
.10 ¬𝑥2,2 ∨ ¬𝑥2,3 .15¬𝑥4,1 ∨ ¬𝑥4,3
.16¬𝑥4,2 ∨ ¬𝑥4,3
24
Graph Coloring Problem
(C) Adjacent vertices must have different colors (for each edge and each
color)
Edges 𝐸 = 1 2 2 3 3 4 4 1
.For each edge 𝑢 𝑣 and color 𝑐 add ¬𝑥𝑢,𝑐 ∨ ¬𝑥𝑣,𝑐 .
For edge (1,2): For edge (3,4):
17. ¬𝑥1,1 ∨ ¬𝑥2,1 23. ¬𝑥3,1 ∨ ¬𝑥4,1
.18¬𝑥1,2 ∨ ¬𝑥2,2 .24¬𝑥3,2 ∨ ¬𝑥4,2
.19¬𝑥1,3 ∨ ¬𝑥2,3 .25¬𝑥3,3 ∨ ¬𝑥4,3
For edge (2,3): For edge (4,1):
20. ¬𝑥2,1 ∨ ¬𝑥3,1 26. ¬𝑥4,1 ∨ ¬𝑥1,1
.21¬𝑥2,2 ∨ ¬𝑥3,2 .27¬𝑥4,2 ∨ ¬𝑥1,2
.22¬𝑥2,3 ∨ ¬𝑥3,3 .28¬𝑥4,3 ∨ ¬𝑥1,3
25
Thank You
26