Generally, a planar map can be modeled as a planar graph. Every country is a member of vertices (u1, u2,..., if two countries vi and u; are adjacent, then there is a edge(ui, Uj) between them. Answer the following questions (9 marks (a) Formalize 4-clolorable problem with predicate logic sentences marks (b) Prove that an infinite map can be still colored with four colors Solution. This is only a reference solution. There are many describing approaches. A grap can be represented as GE<V,E> (a) Let co, C1, C2, c3 be constant to represent 4 colors. (a, c) means a is colored with c.(l mark)E(a, y) means vertices a and y has a edge. is a set of sentences like E(Ui,Ui),vi, UjEV.(1 mark)We can formulate a graph which is 4-colorable with the following sentences i. 1= Va(P(a, co)v P(, c1)v P(a, c2)v P(, c3)). It means that every vertex can be colored with one of 4 colors. (1 mark i.=Vx(∧si≠j≤3-(P(x,C)AP(x,c). A vertex can only be colored with one color. (1 mark i.3= V.iVy(E(x,y)→-(∧o≤κ<3-(P(x,c1)∧P(3,cG)). It means if two vertex are adjacent, they cannot be colored with the same color. (1 mark) (b)2=EUla1, 2, 03) is an infinite set.(1 mark) Consider any finite subset Eo. We an extract vertices Vo from it and construct a set s which describe the graph Go generated by Vo (1 mark) For every finite subgraph is 4-colorable, S is satisfiable Eo must be satisfiable. (I mark) According to compactness theorem, E is satisfiable which means the graph is 4-colorable. (1 markGenerally, a planar map can be modeled as a planar graph. Every country is a member of vertices {v1, v2, . . .}, if two countries vi and vj are adjacent, then there is a edge (vi , vj ) between them. Answer the following questions. (9 marks) (a) Formalize 4-clolorable problem with predicate logic sentences. (5 marks) (b) Prove that an infinite map can be still colored with four colors. (4 marks) Solution. This is only a reference solution. There are many describing approaches. A grap can be represented as G =< V, E >. (a) Let c0, c1, c2, c3 be constant to represent 4 colors. ϕ(x, c) means x is colored with c. (1 mark) E(x, y) means vertices x and y has a edge. E is a set of sentences like E(vi , vj ), vi , vj ∈ V . (1 mark) We can formulate a graph which is 4-colorable with the following sentences: i. ψ1 = ∀x(P(x, c0) ∨ P(x, c1) ∨ P(x, c2) ∨ P(x, c3)). It means that every vertex can be colored with one of 4 colors. (1 mark) ii. ψ2 = ∀x( ∧ 0≤i̸=j≤3 ¬(P(x, ci) ∧ P(x, cj )). A vertex can only be colored with one color.(1 mark) iii. ψ3 = ∀x∀y(E(x, y) → ¬( ∧ 0≤i≤3 ¬(P(x, ci) ∧ P(y, ci)))). It means if two vertex are adjacent, they cannot be colored with the same color.(1 mark) (b) Σ = E ∪ {ψ1, ψ2, ψ3} is an infinite set. (1 mark) Consider any finite subset Σ0. We can extract vertices V0 from it and construct a set S which describe the graph G0 generated by V0.(1 mark) For every finite subgraph is 4-colorable, S is satisfiable. Σ0 must be satisfiable. (1 mark) According to compactness theorem, Σ is satisfiable which means the graph is 4-colorable. (1 mark) 7