How to prove that the bond lattice is a lattice w.r.t. the ordering of refinement

Question

Let $G$ be a graph. Let $L_G$ be the bond lattice of $G$ which consists of all partitions of the vertex set of $G$ in which each part induces a connected subgraph of $G$. How to prove that $L_G$ is a lattice with respect to the ordering of refinement.

I want to prove that $L_G$ has join and meet for any two pair of elements.

Answer 1

Let $G=\langle E,V\rangle$, and let $\mathscr{P},\mathscr{Q}\in L_G$. Let $\mathscr{R}$ be the join of $\mathscr{P}$ and $\mathscr{Q}$ in the lattice of all partitions of $V$; I claim that $\mathscr{R}\in L_G$ and hence is the join of $\mathscr{P}$ and $\mathscr{Q}$ in $L_G$.

Let $\overset{\mathscr{P}}\sim$, $\overset{\mathscr{Q}}\sim$, and $\overset{\mathscr{R}}\sim$ be the equivalence relations associated with $\mathscr{P}$, $\mathscr{Q}$, and $\mathscr{R}$, respectively. Then $u\overset{\mathscr{R}}\sim w$ iff there are $v_0=u,v_1,\ldots,v_n=w\in V$ such that for $k=0,\ldots,n-1$ either

• $v_k\overset{\mathscr{P}}\sim v_{k+1}$ when $k$ is even, and $v_k\overset{\mathscr{Q}}\sim v_{k+1}$ when $k$ is odd, or
• $v_k\overset{\mathscr{Q}}\sim v_{k+1}$ when $k$ is even, and $v_k\overset{\mathscr{P}}\sim v_{k+1}$ when $k$ is odd.

Let $R$ be the element of $\mathscr{R}$ containing $u$ and $w$, and for $k=0,\ldots,n$ let $P_k$ and $Q_k$ be the elements of $\mathscr{P}$ and $\mathscr{Q}$, respectively, containing $v_k$; clearly $R\supseteq\bigcup_{k=0}^n(P_k\cup Q_k)$. The subgraphs induced by the sets $P_k$ and $Q_k$ are connected and interlock, so there is a walk from $u$ to $w$ in the subgraph generated by $\bigcup_{k=0}^n(P_k\cup Q_k)$ and hence in the subgraph generated by $R$. Thus, the subgraph generated by $R$ is connected, and $\mathscr{R}\in L_G$.

Easy examples show that the meet of $\mathscr{P}$ and $\mathscr{Q}$ in $L_G$ is not necessarily their meet in the partition lattice on $V$. For example, if $v_0,v_1,v_2$, and $v_3$ are the vertices of a $4$-cycle, in that order, the meet in $L_G$ of the partitions $\big\{\{0,1,3\},\{2\}\big\}$ and $\big\{\{0\},\{1,2,3\}\big\}$ is the partition into singletons, not $\big\{\{0\},\{2\},\{1,3\}\big\}$.

However, $\mathscr{P}$ and $\mathscr{Q}$ do have a lower bound in $L_G$, namely, the partition into singletons, and we’ve already shown that $L_G$ is a join-semilattice, so the meet of $\mathscr{P}$ and $\mathscr{Q}$ in $L_G$ is simply the join of the lower bounds of $\mathscr{P}$ and $\mathscr{Q}$ in $L_G$. (I am assuming here that $G$ is finite.) This completes the proof that $L_G$ is a lattice.