📂그래프이론

앤더슨-리빙스톤 정리 증명

정리 ¹

$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$

■