📂Graph Theory

Proof of the Anderson-Livingston Theorem

Theorem ¹

$R$ If a commutative ring has a unity $1$ and the set of its zero divisors is denoted as $Z(R)$, then its zero divisor graph $\Gamma (R)$ is a connected graph and $\text{diam}(\Gamma (R)) \le 3$

---

• $\text{diam}$ represents the diameter of a graph.

Explanation

Anderson and Livingstone have made significant contributions to the study of zero divisor graphs, particularly this theorem that specifies the upper limit of graph connectivity and diameter, which is also referred to as the Anderson-Livingstone Theorem.

Proof

Let $x,y \in Z(R) (x \ne y)$.

• Case 1. $xy=0$
  Trivially, $d(x,y)=1$.
• Case 2. $xy \ne 0$
  • Case 2-1. $x^2 = y^2 = 0$
    Hence, $d(x,y)=2$
  • Case 2-2. $x^2 = 0, y^2 \ne 0$
    There exists a $b \in Z(R)$ such that $by=0$.
    • Case 2-2-1. $bx=0$
      Hence, $d(x,y)=2$
    • Case 2-2-2. $bx \ne 0$
      Hence, $d(x,y)=2$
  • Case 2-3. $x^2 \ne 0, y^2 = 0$
    Similar to Case 2-2.
  • Case 2-4. $x^2 \ne 0, y^2 \ne 0$
    There exists a $a, b \in Z(R)$ such that $ax=0=by$.
    • Case 2-4-1. $a=b$
      Since $ax=0=ay$, $d(x,y)=2$
    • Case 2-4-2. $a \ne b$
      • Case 2-4-2-1. $ab=0$
        Hence, $d(x,y)=3$
      • Case 2-4-2-2. $ab \ne 0$
        Hence, $d(x,y)=2$

■