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!


LinkBack URL
About LinkBacks