4 Subgraph implications
Interesting implications between the subgraph equations in Chapter 2. To reduce clutter, trivial or very easy implications will not be displayed here.
Proof
(From MathOverflow). By Definition 2.17, one has the law
\begin{equation} \label{387-again} (x \circ x) \circ y = y \circ x. \end{equation}
1
Specializing to \(y=x \circ x\), we conclude
\[ (x \circ x) \circ (x \circ x) = (x \circ x) \circ x \]
and hence by another application of 2.17 we see that \(x \circ x\) is idempotent:
\begin{equation} \label{idem} (x \circ x) \circ (x \circ x) = x \circ x. \end{equation}
2
Now, replacing \(x\) by \(x \circ x\) in 1 and then using 2 we see that
\[ (x \circ x) \circ y = y \circ (x \circ x) \]
so in particular \(x \circ x\) commutes with \(y \circ y\):
\begin{equation} \label{op-idem} (x \circ x) \circ (y \circ y) = (y \circ y) \circ (x \circ x). \end{equation}
3
Also, from two applications of 1 one has
\[ (x \circ x) \circ (y \circ y) = (y \circ y) \circ x = x \circ y. \]
Thus 3 simplifies to \(x \circ y = y \circ x\), which is Definition 2.14.