Lesson 1

Let us introduce several new numerical characteristics of an undirected graph \(G(V,E)\).

1. \(\alpha(G)\) is the maximum size of a vertex-independent set (or simply independent set), i.e., a set of vertices where no two are connected by an edge: \[\alpha(G)=\max\{|I| \colon I \subseteq V, (\forall u \neq v \in I \colon \{u,v\} \not \in E)\} \ .\] And \(\omega(G)\) is the size of the maximum clique. It is easy to see that \(\alpha(G)=\omega(\overline{G})\), where \(\overline{G}\) is the complement of \(G\).
2. \(\alpha'(G)\) is the maximum size of an edge-independent set, also called a matching, i.e., a set of edges where no two share a common endpoint: \[\alpha'(G)=\max\{|I'| \colon I' \subseteq E, (\forall \{u,v\}\neq \{w,t\} \in I' \colon \{u,v\} \cap \{w,t\}=\varnothing)\} \ .\]
3. \(\beta(G)\) is the minimum size of a vertex cover, i.e., a set of vertices that “touches” every edge: \[\beta(G)=\min\{|C| \colon C \subseteq V, (\forall \{u,v\} \in E \colon \{u,v\} \cap C \neq \varnothing)\} \ .\]
4. \(\beta'(G)\) is the minimum size of an edge cover, i.e., a set of edges that “touches” every vertex (if the graph has isolated vertices, we consider \(\beta'\) undefined or equal to infinity): \[\beta'(G)=\min\{|C'| \colon C' \subseteq E, (\forall v \in V \colon (\exists \{u,w\} \in C' \colon v \in \{u,w\}))\} \ .\]

The following table summarizes the notions of independent sets and covers just introduced.