THE INDUCED PATHS IN A CONNECTED GRAPH AND A TERNARY RELATION DETERMINED BY THEM

Abstract. By a ternary structure we mean an ordered pair (X0,T0), where X0 is a finite nonempty set and T0 is a ternary relation on X0. By the underlying graph of a ternary structure (X0,T0) we mean the (undirected) graph G with the properties that X0 is its vertex set and distinct vertices u and v of G are adjacent if and only if {x ∈ X0; T0(u, x, v)}∪{x ∈ X0; T0(v, x, u)} = {u, v}. A ternary structure (X0,T0) is said to be the B-structure of a connected graph G if X0 is the vertex set of G and the following statement holds for all u, x, y ∈ X0: T0(x, u, y) if and only if u belongs to an induced x − y path in G. It is clear that if a ternary structure (X0,T0) is the B-structure of a connected graph G, then G is the underlying graph of (X0,T0). We will prove that there exists no sentence σ of the first-order logic such that a ternary structure (X0,T0) with a connected underlying graph G is the B-structure of G if and only if (X0,T0) satisfiesσ