무변 그래프

그래프 이론에서 무변 그래프(無邊graph, 틀:Llang)는 꼭짓점을 가질 수 있지만, 변을 가지지 않는 그래프이다.

정의

그래프 $Γ$ 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 그래프를 무변 그래프라고 한다.

꼭짓점이 $n$ 개인 무변 그래프는 완전 그래프 $K_{n}$ 의 여 그래프이므로, ${\bar{K}}_{n}$ 으로 표기될 수 있다.

특히, 꼭짓점이 0개인 무변 그래프 ${\bar{K}}_{0} = K_{0}$ 는 공 그래프(空graph, 틀:Llang)라고 한다.^[1] ${\bar{K}}_{1} = K_{1}$ 은 한원소 그래프(틀:Llang)이다.

무변 그래프의 여 그래프는 (같은 수의 꼭짓점을 갖는) 완전 그래프이다.

완전 그래프가 무변 그래프인 경우는 $K_{0}$ 및 $K_{1}$ 밖에 없다.

무변 그래프는 그 꼭짓점의 수에 따라 분류된다. 즉, 각 기수 $κ$ 에 대하여, $κ$ 개의 꼭짓점을 갖는 무변 그래프 ${\bar{K}}_{κ}$ 가 존재하며, 동형 아래 유일하다.