Hypergraph $2$-colorability is NP-complete So far all my searches for a proof of this well-known theorem have led me to the one below (Lovász 1973), reducing $k$-colorability for ordinary graphs to $2$-colorability for hypergraphs.

In the construction, $H$ seems to contain copies of $G$, so its chromatic number should be higher than that of $G$, contrary to the last claim. If I'm not mistaken, I would guess the proof can be easily corrected. But I haven't found the correction yet.
 A: Here is a reduction, but I'm not sure it's the one Lovász had in mind...
Let $y$ and $z$ be two new points. Let the hyperedges of $H$ consist of


*

*$\{y,z\}$

*$\{x_{i\mu},x_{i\nu},z\}$ ($1 \leq i \leq k$) when $\{x_{\mu},x_{\nu}\}$ is an edge from $G$

*$f_\nu = \{x_{1\nu},\ldots,x_{k\nu},y\}$ ($1 \leq \nu \leq n$) as described by Lovász


Suppose we have a {red,blue}-coloring of the resulting hypergraph $H$. Without loss of generality, $y$ is colored red and $z$ is colored blue (they can't be of the same color because of the hyperedge $\{y,z\}$). 
Note that the set of vertices $B_i$ from the original graph $G$ that are colored blue in the copy $G_i$ form an independent set for if $B_i$ contained an edge $\{x_{\mu},x_{\nu}\}$ then the hyperedge $\{x_{i\mu},x_{i\nu},z\}$ would be all blue.
Looking at the hyperedge $f_\nu = \{x_{1\nu},\ldots,x_{k\nu},y\},$ we see that at least one of $x_{1\nu},\ldots,x_{k\nu}$ must be colored blue, else the hyperedge $f_\nu$ would be all red. Therefore, every vertex of the original graph is contained in some $B_i$.
So we have a cover of $V(G)$ with $k$ independent sets $B_1,\ldots,B_k$, which means that $G$ is $k$-colorable. Reversing the process, we can go from a $k$-coloring of $G$ to a {red,blue}-coloring of $H$.
