quotient graph $G^R$

Question

I understand that if $R$ is an equivalence relation on $G$, the resulting partition cells are either equal or disjoint. I think I understand that the graph of the quotient set $G^R$ is constructed with a representative vertex from each cell.

Then, why does $G^R$ have edges if the cells are disjoint?

Answer 1

Suppose that $C_0$ and $C_1$ are distinct cells of the partition, with representative vertices $v_0$ and $v_1$, respectively. Then in $G^R$ there is an edge $v_0v_1$ if and only if there is at least one edge of $G$ joining a vertex in $C_0$ and a vertex in $C_1$. For a simple example, let $G$ be the graph shown below:

             a   b   c   d
             *---*---*---*  
             |   |   |  
             *---*---*  
             e   f   g

Partition the vertices of $G$ into cells $\{a,e\},\{b,f\},\{c\}$, and $\{d,g\}$, and let $a,b,c$, and $d$ be the representatives of these cells.

• $G$ has at least one edge between $\{a,e\}$ and $\{b,f\}$ — two in fact — so $G^R$ has an edge between $a$ and $b$.
• $G$ has an edge between $\{b,f\}$ and $\{c\}$, so $G^R$ has an edge between $b$ and $c$.
• $G$ has an edge (two, in fact) between $\{c\}$ and $\{d,g\}$, so $G^R$ has an edge between $c$ and $d$.
• Finally, $G$ has an edge between $\{b,f\}$ and $\{d,g\}$, so $G^R$ has an edge between $b$ and $d$.

That accounts for all of the edges of $G$ that link different cells, so it accounts for all of the edges of $G^R$. $G^R$ therefore looks like this:

             a   b   c   d  
             *---*---*---*  
                 |_______|  

Or if you prefer, like this:

                    *c    
                   /|
             a   b/ |
             *---*  |  
                  \ |  
                   \|  
                    *d