# How many edge covers are there for a complete graph?

An edge cover of a graph $G = (V,E)$ is set $E' \subseteq E$ of edges such that for every vertex $v \in V$ there exists an edge $e \in E'$ such that $v \in e$.

Examples:

1. E is trivially an edge cover.
2. $\{\{1,2\},\{3,4\},\{1,5\}\}$ is an edge cover of $K_5$, the complete graph over 5 vertices.

Computing the total number of edge covers for any graph is #P-complete (from here).

I want to know the answer to a specialized version: What is the total number of edge covers of $K_n$, the complete graph on $n$ vertices?

This is a really hard problem for general graphs.

To give a sense, let's look at the behavior of $E(G)$, the number of edge coverings of $G$, on a couple of simple families of graphs.

First consider $A_n$, the connected graph on $n$ vertices in which one vertex has degree $n-1$ and all other vertices have degree $1$.
Of course we have $$E(A_n) = 1$$

Next consider the linear graphs $L_n$, which are the cyclic graphs $C_n$ with one edge removed.
For this family one can show via simple inductive argument that the number of edge coverings is $$E(L_n) = F_{n-1} \sim \frac{\varphi^{n-1}}{\sqrt{5}}$$ where $F_n$ is the $n$th Fibonacci number and $\varphi$ is the golden ratio. (Similarly $E(C_n)$ is the $n$th Lucas number.)

Lastly consider the complete graphs $K_n$, for which one can show that the number of edge coverings are $$E(K_n) = \sum\limits_{j=0}^{n}(-1)^j{n \choose j} 2^{n-j \choose 2} \sim 2^{\frac{n(n-1)}{2}}$$

Note $A_n$ and $L_n$ have the same number of vertices and edges but totally different numbers of edge coverings, showing that we need detailed information about at least the degree sequence of a graph. A degree $0$ (isolated) vertex forces $E(G) = 0$ immediately; a degree $1$ vertex contributes no freedom to the edge covering; but increasing a degree $1$ vertex to degree $2$ more or less doubles the number of edge covers, i.e. the problem is inherently exponential.

$E(K_n)$ gives an upperbound on $E(G)$ for $|G| = n$, if we are considering graphs in which the edge set is not allowed to be a multiset.

You might want to check out this paper: https://cs.uwaterloo.ca/journals/JIS/VOL11/Tauraso/tauraso18.html