Results 1 to 1 of 1

Math Help - Independence number and clique number (prove)

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    43

    Independence number and clique number (prove)

    Prove that following statement is true:

    α(G)+ω(G) ≥ n +1

    where
    α(G):= is the number of vertices in an independent set of maximum order (an independent set is a subset of vertices, no two of which are adjacent)
    ω(G):= the number of vertices in a maximum clique of G
    n:= the number of vertices in the G graph

    Thank you in advance!
    Last edited by zadir; November 18th 2010 at 01:51 PM. Reason: I mistyped the statement! Sorry, it's n+1, not only n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: February 12th 2011, 06:02 AM
  2. Replies: 0
    Last Post: February 16th 2010, 06:04 AM
  3. Prove there is a number a
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: January 11th 2010, 02:08 PM
  4. Replies: 6
    Last Post: November 16th 2009, 03:42 PM
  5. Replies: 1
    Last Post: April 17th 2009, 02:34 PM

Search Tags


/mathhelpforum @mathhelpforum