📂Graph Theory

Proof of the Anderson-Livingston Theorem

Theorem¹

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

---

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

Explanation

Anderson and Livingston made important contributions to the study of zero-divisor graphs, and in particular, this theorem, which establishes the connectivity of the graph and an upper bound on its diameter, is also called the Anderson-Livingston 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$
    Therefore $d(x,y)=2$
  • Case 2-2. $x^2 = 0, y^2 \ne 0$
    There exists $b \in Z(R)$ such that $by=0$.
    • Case 2-2-1. $bx=0$
      Therefore $d(x,y)=2$
    • Case 2-2-2. $bx \ne 0$
      Therefore $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 exist $a, b \in Z(R)$ such that $ax=0=by$.
    • Case 2-4-1. $a=b$
      Since $ax=0=ay$, we have $d(x,y)=2$
    • Case 2-4-2. $a \ne b$
      • Case 2-4-2-1. $ab=0$
        Therefore $d(x,y)=3$
      • Case 2-4-2-2. $ab \ne 0$
        Therefore $d(x,y)=2$

■