Results 1 to 2 of 2

Math Help - Intro to graph theory

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    38

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by lacy1104 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Understanding a solution -- intro to ring theory -- ideals
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 6th 2011, 09:11 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  3. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM
  5. Algebra help in Hardy's 'Intro to Number Theory'
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 5th 2010, 06:39 PM

Search Tags


/mathhelpforum @mathhelpforum