Magic Graphs

A $k$-partite graph is a graph whose vertices can be partitioned into $K$ disjoint sets so that no two vertices within the same set are adjacent. In this problem we consider a special version of a $k$-partite graph in which each disjoint set contains exactly two vertices. Let us call this graph magic graph. In what follows we characterize such magic graphs.

Let $P$ be a set of positive labels \{1, 2, 3, 4, \ldots\} and $N$ be a set of negative labels \{1', 2', 3', 4', \ldots\}. Also let L = P \cup N. A magic graph is a k-partite graph G = (V, E), where $V$ is a set of vertices and E is a set of edges. We define V = V_1 \cup V_2 \cup V_3 \cup \ldots \cup V_k, where each V_i is a subset of $L$ and |V_i| = 2. There is an edge \{l_1, l_2\} in $G$ if and only if l_1 and l_2 are in different vertex sets and l_1 and l_2 are not positive and negative labels of the same number. For instance, the following graph is a magic graph.

This graph is a tripartite magic graph. V_1 is $\{1,2\}$. V_2 is \{1', 2'\}. V_3 is \{1, 2'\}. Note that multiple nodes may have the same label. For example, the node labeled $1$ in V_1 is a not the same node as the node labeled $1$ in V_3. The edges follow the rule above. For example, there are edges $\{1,1\}$ and \{1, 2'\} because the labels are in different vertex sets and they are not positive and negative labels of the same number. Observe that edge \{1, 1'\} does not exist because the two labels are positive and negative labels of the same number.

Given a $k$-partite magic graph $G$, your job is to find whether there exists a $k$-clique in $G$.