As regards this post Maximal independent sets in a graph $G$ versus maximal matchings in the line graph $L(G)$ -- and in particular, the comments under this answer https://math.stackexchange.com/a/1125634/963553 -- I would like to ask:
What if we assume that $G$ is connected (and we want to find a maximum independent set in $G$)? $~$Are there instances of M.I.S. where there is no bijection between $I$ (an independent set) in $G$ and a matching $M$ (the set of matched edges) in the line graph $L(G)$?
(From a computational complexity perspective, an instance of $G$ that is "arbitrarily large" would be better -- then we'll know for sure that such a bijection is impossible when the size of $G$ increases indefinitely.)
$P.S.$: $~$An interesting observation is that the basic feasibility conditions of both problems (M.I.S. and maximum cardinality matching) can be expressed as Horn formulas (a conjunction of Horn clauses) where every literal is negative -- even though one problem is NP-hard and the other is polynomially solvable.. For example, for M.I.S., for every edge $(x,y)$, we express $[\neg F(x) \lor \neg F(y)]$, where $F(x)$ is true iff vertex $x$ is a member of the independent set $I$.
For max. cardinality matching, for every vertex $x$, and assuming that $M(x,y)$ is true iff the edge $(x,y)$ is matched, we write:
$\displaystyle \forall \, ({y, z~|~(x,y), ~(x,z) \in E \land (y \ne z)}) ~~ [\neg M(x,y) \lor \neg M(x,z)].$
(These Horn formulas can be converted to Integer Programs and vice versa.)
Take $G$ to be the $(n+1)$-vertex star graph $K_{1,n}$. Then $L(G) = K_n$.
There are $2^n+1$ independent sets in $G$: we can pick the center of the star (and then nothing else), or we can avoid picking the center, and then any subset of the other vertices is an independent set.
There are many more matchings in $L(G)$: the number of matchings of size $k$ is $$ \frac{\binom n2 \binom{n-2}{2} \binom{n-4}{2}\dotsm \binom{n-2k+2}{2}}{k!} = \frac{n!}{k!(n-2k)!2^k}. $$ Even the number of perfect matchings when $n$ is even, $\frac{n!}{(n/2)! 2^{n/2}}$, grows faster than exponential.