Definability of graphs by congruence lattices (Q912136)

An undirected graph is an ordered pair \(<G,\tau >\), where G is the vertex set and \(\tau\) is the adjacency relation. The symbol P(G\(\times G)\) denotes the lattice of all subsets of the set \(G\times G\); further, \(C(G)=P(G\times G)\times P(G\times G)\). An element \(\theta =<\theta^ 0,\theta^ 1>\in C(G)\) is a congruence on G if \(\theta^ 0\) is an equivalence relation on G and further \(\tau \subseteq \theta^ 1\) and \(<x,u>\in \theta^ 0\), \(<y,v>\in \theta^ 0\), \(<x,y>\in \theta^ 1\) imply \(<u,v>\in \theta^ 1.\) The symbol \({\mathcal S}\) denotes the quasivariety of undirected graphs without loops. For \(G\in {\mathcal S}\) the congruences \(\theta\) satisfying G/\(\theta\in {\mathcal S}\) form the lattice \(Con_{{\mathcal S}}G\). The symbol \(G^*\) denotes the graph obtained from G by deleting all vertices which are adjacent to all others. Theorem: If G and \(G_ 1\) are incomplete graphs, then \(Con_{{\mathcal S}}G\cong Con_{{\mathcal S}}G_ 1\) if and only if \(G^*\cong G^*_ 1\). A graph G is complete if and only if \(| Con_{{\mathcal S}}G| =2\).