We are given a $n$-partite weighted graph $G$. Each partition has $n$ vertices, some of which may be isolated. Each partition must contain at least one non-isolated vertex. Let us number the vertices in some $i^{th}$ partition as $V\_{i1},V\_{i2},...,V\_{in}$. Now each non-isolated vertex $V\_{ij}$ has a set of $n-1$ neighbors (one in each of the remaining $n-1$ partitions) that form a permutation with $j$. Vertex $V\_{ij}$ can have other neighbors as well. In fact it can have several such sets of neighbors.


Every non-isolated vertex has a positive weight $w\_{ij}$ and every edge $(V\_{ij},V\_{kl})$ has a positive weight $e\_{ijkl}$. For every non-isolated vertex $V\_{ij}$, the following must be true $w\_{ij}=\sum\_{l}e\_{ijkl}\forall k(\neq i)=\sum\_{k}e\_{ijkl}\forall l(\neq j)$. As a consequence of this condition, if a vertex has only one neighbor at position $l$ (of some partition $k$) among all partitions, then it cannot have any other neighbor in that partition $k$. Also, if a vertex has only one neighbor in some partition $k$ (at some position $l$), then it cannot have any neighbor at that position in any other partition.


We conjecture that the graph $G$ will always contain a $n$-clique. Is it true?



"n-partite n-clique" with added conditions
Take $n$ prime and connect $(i,j)$ with $(k,l)$ if $(i-k)(j-l)\equiv 1\mod n$. Clearly, each vertex has one neighbor in each row and column except its own. Also, if $xy=1$ and $zt=1$ in $\mathbb Z\_n$, then there is no reason to expect that $(x-z)(y-t)=1$ (actually, if $-3$ is not a quadratic residue modulo $n$ (say, $n=5$), it is not merely unlikely but plainly impossible, so this graph contains no triangles, leave alone $n$-cliques.


Now, what are you really after? 


