Thread: 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)

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 , then there exists an element . But then this means k~x and k~y. But this would mean x~y and thus .

(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 and that means .