I can. But my proof uses a theorem (which I do not reveal yet to avoid influencing you) and it feels like an overkill, so I wonder if there is a simple proof. Now the problem.


Suppose we have a hypergraph on n vertices with n-1 edges. Can we color some (at least one) of its vertices with red and blue such that every hyperedge either contains both colors, or all of its vertices are uncolored?


The motivation is [this](http://lemon.cs.elte.hu/egres/open/Problem_of_the_month_May_2011) question. In fact, one can similarly define partial k-polychromatic coloring, where every hypergraph with less than n/(k-1) edges seems to be partially k-colorable, if my proof is correct. Note also that these bounds are tight as shown by disjoint edges of size k-1. And this cannot be improved by requiring some lower bound on the size of each hyperedge, as we observed yesterday with my usual set of friends, Cory, Dani, Keszegh, Nathan and Patkos.


Please do not post links to Beck-Fiala and other well-known, similar theorems! At the moment I am only interested in a short, elementary proof of my question.



Can you prove that hypergraphs with n-1 edges are partially 2 colorable?
Let $E\_1,\ldots, E\_j$ be the sets of edges spanning vertex sets $S\_1,\ldots,S\_j$ such that for each $i$ in $[j]$, $|S\_i|\leq |E\_i|$. Let $S'$ and $E'$ be their respective unions. We will leave $S'$ uncoloured.


Let $G'$ be the subhypergraph of $G$ reached by deleting $S'$ (here if an edge of $G$ partially intersects $S'$, it may still exist in $G'$). Observe that in $G'$, there is no set of $k$ edges spanning at most $k$ vertices for any $k$. For now assume that $G'$ is connected. Take some vertex $v$ of $G'$ and delete it to reach $G''$. By Hall's theorem, we can now find an injection from the vertices of $G''$ to the (nonempty) edges of $G''$.


We can now find a spanning tree ordering of the edges of $G'$ with the root being some vertex of $G''$ that is in an edge with $v$. Give $v$ colour $1$. We traverse the tree in, say, DFS ordering, and when we come to an edge $e$, we choose for its matched vertex $v\_e$ a colour that will make $e$ dichromatic.


If $G'$ is not connected we do the same thing with each connected component.


