The focus is on the use of Datalog for defining properties and queries on graphs.
(a) Assume that P is some property of graphs definable in the Datalog. Show that P is preserved beneath extensions and homomorphisms. That is, when G is a graph satisfying P, then for every supergraph of G (i.e., graph extending G) satisfies P, and when h is a graph homomorphism, then h(G) satisfies P. Which of the below properties and queries on graphs are definable in the Datalog?
(b) The number of vertices are even.
(c) There is a simple path (that is, a path without repeated vertices) of even length among two specified vertices.
(d) The binary relation? Having all pairs of vertices (a, b) for which there is a path of even length from a to b.
Given either a Datalog program stating the property or query or an argument why the property or query is not definable in the Datalog.