📂グラフ理論

アンダーソン・リビングストン定理の証明

定理¹

$R$が単位元$1$を持つ可換環であり、その零因子の集合を$Z(R)$とすると、その零因子グラフ$\Gamma (R)$は連結グラフであり、$\text{diam}(\Gamma (R)) \le 3$

---

• $\text{diam}$はグラフの直径を意味する。

説明

アンダーソンとリビングストンは零因子グラフの研究において重要な業績を残しており、特にグラフの連結性と直径の上限を特定するこの定理をアンダーソン・リビングストン定理と呼ぶこともある。

証明

$x,y \in Z(R) (x \ne y)$としよう。

• Case 1. $xy=0$
  自明に$d(x,y)=1$である。
• Case 2. $xy \ne 0$
  • Case 2-1. $x^2 = y^2 = 0$
    したがって$d(x,y)=2$
  • Case 2-2. $x^2 = 0, y^2 \ne 0$
    $by=0$となる$b \in Z(R)$が存在する。
    • Case 2-2-1. $bx=0$
      したがって$d(x,y)=2$
    • Case 2-2-2. $bx \ne 0$
      したがって$d(x,y)=2$
  • Case 2-3. $x^2 \ne 0, y^2 = 0$
    Case 2-2と同様である。
  • Case 2-4. $x^2 \ne 0, y^2 \ne 0$
    $ax=0=by$となる$a, b \in Z(R)$が存在する。
    • Case 2-4-1. $a=b$
      $ax=0=ay$なので$d(x,y)=2$
    • Case 2-4-2. $a \ne b$
      • Case 2-4-2-1. $ab=0$
        したがって$d(x,y)=3$
      • Case 2-4-2-2. $ab \ne 0$
        したがって$d(x,y)=2$

■