# Intro to graph theory

• May 7th 2008, 09:08 AM
lacy1104
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 http://www.cramster.com/Answer-Board...2662508592.gif. In other words two of the sets C(x) and C(y) cannot intersect unless they are equal.

ii) if http://www.cramster.com/Answer-Board...2662508592.gif, then there does not exist an edge joining a vertex in C(x) to a vertex in C(y)
• May 7th 2008, 10:28 AM
Isomorphism
Quote:

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 http://www.cramster.com/Answer-Board...2662508592.gif. In other words two of the sets C(x) and C(y) cannot intersect unless they are equal.

ii) if http://www.cramster.com/Answer-Board...2662508592.gif, then there does not exist an edge joining a vertex in C(x) to a vertex in C(y)

(i)If $\displaystyle C(x) \cap C(y) \neq \phi$, then there exists an element $\displaystyle k \in C(x) \cap C(y)$. But then this means k~x and k~y. But this would mean x~y and thus $\displaystyle 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 $\displaystyle x \in C(y)$ and that means $\displaystyle x \in C(x) \cap C(y)\Rightarrow C(x) \cap C(y) \neq \phi$.