independent set and independence number IndependentSetAndIndependenceNumber 2004-07-27 17:05:15 2006-11-10 15:21:13 Definition independent set independence number % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here A set of vertices in a graph $G$ is called an {\em independent set} if there are no edges between the vertices. The {\em independence number} of a graph $G$, usually denoted by $\alpha(G)$, is the size of a maximal independent set in $G$. $\alpha(G) \geq \nu$ means that there are $\nu$ vertices with no edges between them. An independent set is sometimes called a stable set or an anticlique.