On the number of components of a graph

Abstract

Let $G:=(V,E)$ be a simple graph; for $I\subseteq V$ we denote by $l(I)$ the number of components of $G[I]$, the subgraph of $G$ induced by $I$. For $V_1,\ldots , V_n$ subsets of $V$, we define a function $\beta (V_1,\ldots , V_n)$ which is expressed in terms of $l\left(\bigcup _{i=1} ^{n} V_i\right)$ and $l(V_i\cup V_j)$ for $i\leq j$. If $V_1,\ldots , V_n$ are pairwise disjoint independent subsets of $V$, the number $\beta (V_1,\ldots , V_n)$ can be computed in terms of the cyclomatic numbers of $G\left[\bigcup _{i=1} ^{n} V_i\right]$ and $G[ V_i\cup V_j]$ for $i\neq j$. In the general case, we prove that $\beta (V_1,\ldots , V_n)\geq 0$ and characterize when $\beta (V_1,\ldots , V_n)= 0$. This special case yields a formula expressing the length of members of an interval algebra \cite{s} as well as extensions to pseudo-tree algebras. Other examples are given.