How to calculate the number of graphs without vertices of degree 0 using inclusion-exclusion principle?

Question

So there is this homework question where we have to determine the number of graphs with no vertices of degree 0 using the inclusion-exclusion principle. With $V = {1, 2, ... n}$ and the answer should be a function of n.

I know this is the inclusion-exclusion principle rule and that the total number of graphs possible is $2^{\binom{n}{2}}$. So that would be $|A_1| + |A_2| + ... + |A_n|$.

$$\left| \bigcup_{i = 1}^{n} A_i \right| = \sum_{k = 1}^{n} (-1)^{k - 1} \sum_{I \in \binom{\{1, 2, \ldots, n\}~}{k}} \left| \bigcap_{i \in I} A_i\right|$$

But I don't really know what $|A_1 \cap A_2|$ is supposed to mean/be in this example and neither the others. Can someone help me with this?

Answer 1

You can think $|A_i|$ as the number of graphs that for the vertex $i$ with $1 \le i \le n$, $d(i)=0$. In this case, if we give an example, $|A_1 \cap A_2|$ is the number of graphs that vertex $1$ and $2$ both has degree of $0$. What you want to do is to find the number of graphs with at least one vertex with degree zero and subtract it from the number of total graphs you can have, which is as you stated, $2^{\binom{n}{2}}$. Here, I can say that for each $i$, $|A_i| = 2^{\binom{n-1}{2}}$ because we are removing all the edges connected to $i$ in order to make $d(i) = 0$ and construct a new graph with remaining edges and $n-1$ vertices. Similarly, $|A_1 \cap A_2| = 2^{\binom{n-2}{2}}$ and so on. Now you can use Inclusion-Exclusion Principle to find the number of bad graphs (the graphs that have at least one vertex with degree zero). So your answer should be $$2^{\binom{n}{2}} - |\bigcup \limits_{i=1}^{n}A_{i}| =\sum \limits_{k=0}^{n}{(-1)^k\binom{n}{k}2^{\binom{n-k}{2}}}$$

Note that I also included the term $2^{\binom{n}{2}}$ to the sum.

Answer 2

Assuming we're not considering if graphs are isomorphic, here is my attempt at a formal proof:

Let $C = \{ G = (V, E) : \forall v \in V(G),$ $\deg_G(v) \neq 0\}$, which is the set of all graphs that have no vertices of degree $0$. Now consider the complement of this set $\overline{C} = \overline{C}_1 \cup \overline{C}_2 \cup \cdots \cup \overline{C}_n$ where $\overline{C}_i = \{ G = (V,E) : \deg_G(v_i) = 0\} \: (i \in \{1,...,n\})$. In other words $\overline{C}$ is the set of all graphs that have at least one vertex of degree $0$. Since for all $G \in \overline{C}_i$, $G$ has an edge set such that $\forall j \in \{1,...,n\} \setminus \{i\}$, $\{v_i, v_j\} \notin E(G)$ (i.e. $v_i$ is fixed with no edges), we can instead consider the number of possible graphs on $V(G) \setminus \{v_i\}$ since there are no combinations of edges containing $v_i$ that will induce a new graph. Thus, $$|\overline{C}_i| = 2^{{|V(G) \setminus \{v_i\}| \choose 2}} = 2^{{n - 1 \choose 2}}.$$

We apply the same intuition to some arbitrary intersection $$\overline{C}_{i_1} \cap \overline{C}_{i_2} \cap \cdots \cap \overline{C}_{i_k} \: (i_j \in \{1, ..., n\}, \: j \in \{1,...,k\}, \: k \leq n).$$ Since $\overline{C}_{i_1} \cap \overline{C}_{i_2} \cap \cdots \cap \overline{C}_{i_k} = \{ G = (V, E) : \{v_{i_1},...,v_{i_k}\} \subseteq V(G) \text{ and } \displaystyle\sum_{v \in \{v_{i_1},...,v_{i_k}\}} \deg_G(v) = 0\}$, we need only consider the number of graphs on the vertex set $V(G) \setminus \{v_{i_1}, ..., v_{i_k}\},$ since all $v \in \{v_{i_1},...,v_{i_k}\}$ are fixed with degree $0$. Consequently, $$|\overline{C}_{i_1} \cap \overline{C}_{i_2} \cap \cdots \cap \overline{C}_{i_k}| = 2^{{|V(G) \setminus \{v_{i_1},...,\: v_{i_k}\}| \choose 2}} = 2^{{n - k \choose 2}}.$$

We define such a property because there is, of course, overlap between the sets $\overline{C}_{i}$, so we apply the inclusion exclusion principle as follows:

$$|\overline{C_1} \cup \overline{C_2} \cup \cdots \cup \overline{C_n}| = \displaystyle\sum_{k = 1}^{n} (-1)^{k - 1} \displaystyle\sum_{I \in \binom{[n]}{k}} \left\lvert \bigcap_{i \in I} \overline{C_i} \right\rvert = \displaystyle\sum_{k = 1}^{n} (-1)^{k - 1} {n \choose k} 2^{{n - k \choose 2}}.$$ (We multiply $2^{{n - k \choose 2}}$ by ${n \choose k}$ because there are ${n \choose k}$ ways to choose a $k$-element subset $\{v_{i_1},...,v_{i_k}\} \subseteq V(G)$ such that $\displaystyle\sum_{v \in \{v_{i_1},...,v_{i_k}\}} \deg_G(v) = 0$).

Recall, however, that this is the number of graphs with at least one vertex of degree $0$. Thus, the number of graphs with no vertices of degree $0$ is

$$|C| = 2^{n \choose 2} - \displaystyle\sum_{k = 1}^{n} (-1)^{k - 1} {n \choose k} 2^{{n - k \choose 2}}.$$

Side note:

In this proof, I'm assuming you know that the number of possible graphs on some vertex set $V$ is $2^{{|V| \choose 2}}$. If you aren't familiar with this, the basic idea of proving this would be to understand that ${V \choose 2}$ gives us all possible edges on the given vertex set $V$, so to find the number of possible graphs on $V$, we are counting the number of possible mappings, $f$, such that each mapping uniquely maps the set ${V \choose 2}$ to the set $\{1, 0\}$ (for some $e \in {V \choose 2}$, $f(e) = 1$ denotes the edge is included in the edge set of the graph and $f(e) = 0$ denotes it is not). This would be $$|\{1, 0\}|^{|{V \choose 2}|} = 2^{{|V| \choose 2}}$$.

More on total mappings from an m-element set to an n-element set: How many functions are there from a set with $m$ elements to a set with $n$ elements?