Editing Independent set (graph theory) (section)

===Relationship to other graph parameters===

A set is independent if and only if it is a [[Clique (graph theory)|clique]] in the graph’s [[Complement graph|complement]], so the two concepts are complementary. In fact, sufficiently large graphs with no large cliques have large independent sets, a theme that is explored in [[Ramsey theory]].

A set is independent if and only if its complement is a [[vertex cover]].<ref>Proof: A set V of vertices is an independent set. if and only if every edge in the graph is adjacent to at most one member of V, if and only if every edge in the graph is adjacent to at least one member not in V, if and only if the complement of V is a vertex cover.</ref> Therefore, the sum of the size of the largest independent set <math>\alpha(G)</math> and the size of a minimum vertex cover <math>\beta(G)</math> is equal to the number of vertices in the graph.

A [[Graph coloring|vertex coloring]] of a graph <math>G</math> corresponds to a [[Partition of a set|partition]] of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the ''chromatic number''  <math>\chi(G)</math>, is at least the quotient of the number of vertices in <math>G</math> and the independent number <math>\alpha(G)</math>.

In a [[bipartite graph]] with no isolated vertices, the number of vertices in a maximum independent set equals the number of edges in a minimum [[edge covering]]; this is [[Kőnig's theorem (graph theory)|Kőnig's theorem]].