# Thread: Intro to graph theory

1. ## Intro to graph theory

For each vertex x, let C(x) ={z:x~z}. Prove the following:

i) For all vertices x and y, either C(x)=C9Y) or else . In other words two of the sets C(x) and C(y) cannot intersect unless they are equal.

ii) if , then there does not exist an edge joining a vertex in C(x) to a vertex in C(y)

2. Originally Posted by lacy1104
For each vertex x, let C(x) ={z:x~z}. Prove the following:

i) For all vertices x and y, either C(x)=C9Y) or else . In other words two of the sets C(x) and C(y) cannot intersect unless they are equal.

ii) if , then there does not exist an edge joining a vertex in C(x) to a vertex in C(y)
(i)If $C(x) \cap C(y) \neq \phi$, then there exists an element $k \in C(x) \cap C(y)$. But then this means k~x and k~y. But this would mean x~y and thus $C(x) = C(y)$.

(ii)Say there exists an edge uv joining u in C(x) to v in C(y), then consider any vertex x in C(x), u~x. But since u~v, so x~v. Thus $x \in C(y)$ and that means $x \in C(x) \cap C(y)\Rightarrow C(x) \cap C(y) \neq \phi$.