Intersecting solutions

Question

The following problem is one of those I give to my students as a homework trying to test their combinatorial skills. It is one of those technically routine "intermediate" statements one has to prove analyzing some general problem. I am consciously omitting any context and publish it here (hopefully not against the rules) just as an invitation to talk on pure combinatorics and graphs and on how you manage to solve finitistic problems which seem to be beyond algebraic (or other powerful) methods.

Define the following graph $(\mathcal{V},\mathcal{E})$ called supercastle. Let $\textbf{X}=[3]×[3]$ with $[n]$ standing for $\{1,…,n\}$. For $u=(u_1,u_2)∈\textbf{X}$, define and denote a $u$-part as $R_u=\{u_1\}×\{u_2\}×[5]×[2]$. Then $\textbf{Y}=⋃_{u∈\textbf{X}}R_u$ and $\mathcal{V}=\textbf{X}∪\textbf{Y}$. For $u,v∈\textbf{X}$, consider the Hamming distance $d(u,v)=|\{i∈[2]:u_i=v_i\}|$. To define $\mathcal{E}$, consider the following three cases for distinct $u,v∈\mathcal{V}$:

1. $u,v∈\textbf{X}:\{u,v\}∈\mathcal{E}⇔d(u,v)=1$
2. $u∈\textbf{X},v∈\textbf{Y}:\{u,v\}∈\mathcal{E}⇔v∈R_u$
3. $u,v∈\textbf{Y}:\{u,v\}∈\mathcal{E}⇔u_1=v_1∧u_2=v_2∧u_3=v_3∨d((u_1,u_2 ),(v_1,v_2 ))=1∧u_3=v_3∧u_4=v_4$

Define a diamond as a graph isomorphic to one of the following graphs:

1. $([4],\{\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{3,4\}\})$ (type 1 diamond)
2. $([5],\{\{1,2\},\{1,3\},\{1,4\},\{2,5\},\{3,5\},\{4,5\}\})$ (type 2 diamond)

Let $u,v,w∈\textbf{X}$ and $d(u,v)=d(u,w)=d(v,w)=2$. Let us call a $(u,v,w)$-solution the following subset $S⊆\mathcal{P}_2(R_u∪R_v∪R_w )$ with $\mathcal{P}_2(A)$ standing for the set of all $2$-subsets of $A$:

1. For all $\{x,y\}∈S$, $x$ and $y$ belong to distinct parts (say, if $x∈R_u$, then $y∉R_u$).
2. For all $\{x,y\}∈S$, there is a unique $z∈R_u∪R_v∪R_w$ such that $\{x,z\},\{y,z\}∈S$.
3. For all distinct $a,b∈\{u,v,w\}$ and $x∈R_a$, there are exactly two elements $y,z∈R_b$ such that $\{x,y\},\{x,z\}∈S$.
4. The graph $(\mathcal{V},\mathcal{E}∪S)$ contains no diamonds.

Let $S$ is a $(u,v,w)$-solution and $S'$ is a $(u',v',w')$-solution. Let us say $S$ and $S'$ correlate if $(\mathcal{V},\mathcal{E}∪S∪S')$ contains no diamonds. Also, let us say $S$ and $S'$ are intersecting and non-intersecting if $|\{u,v,w\}∩\{u',v',w'\}|=1$ and $|\{u,v,w\}∩\{u',v',w'\}|=0$ respectively. One may show that all non-intersecting solutions correlate. Prove or disprove that all intersecting solutions do not correlate (which will be the answer).

P. S. It can be shown that this answer given by Rob Pratt (who effectively used integer linear programming) implies there is always a $(u,v,w)$-solution for all $u,v,w∈\textbf{X}$ such that $d(u,v)=d(u,w)=d(v,w)=2$.

Answer 1

I have found a computer proof of the statement that there are no two intersecting solutions $S$ and $S'$ which correlate. Again, integer linear programming has been used (though, to disprove a statement). The idea is as follows. Consider the graph $G=(V,E)$ such that $V=[3]\times[3]\cup[3]\times[3]\times[5]\times[2]$ and

\begin{align}\forall(x,y\in[3]\times[3]):\{x,y\}\notin E\end{align} \begin{align}\forall(x\in[3]\times[3])\forall(y\in[3]\times[3]\times[5]\times[2]):\{x,y\}\in E⇔x_1=y_1\wedge x_2=y_2\end{align} \begin{align}\forall(\{x,y\}\in\mathcal{P}_2([3]\times[3]\times[5]\times[2])):\{x,y\}\in E⇔x_1=y_1\wedge x_2=y_2\wedge x_3=y_3\end{align}

Assume some solutions $S$ and $S'$ are intersecting and correlate. This implies one can add in $G$ two edges going from each vertex $x\in\{1\}\times\{1\}\times[5]\times[2]$ to each set $\{i\}\times\{j\}\times[5]\times[2]$ with $i,j\in\{2,3\}$ such that the new graph contains no diamonds. Trying to perform this addition in python leads to the infeasible problem (status $-1$). I will be really glad to your comments on the correctness of such kind of proofs.