An undirected edge joins two vertices of the direct product graph G × = G × G iff (i) the two involved vertices of G are joined by an edge in E and (ii) the two involved vertices of G are joined by an edge in E and (iii) these two edges in E and E have the same label: