$G$ a graph such that for any $S⊆V$ we have $|E(G[S])| ≤ k|S|$

Question

I am struggling with the following problem for a while now and I am in need of a little hint:

Let $k≥1$ be an integer and $G(V,E)$ a (simple, undirected) graph such that for any $S⊆V$ we have $|E(G[S])| ≤ k|S|$. Show that it is possible to assign an orientation to every edge of G in such a way that any vertex in V belongs to at most k edges directed away from it.

I believe it might have something to do with Hall's Theorem, because the condition $|E(G[S])| ≤ k|S|$ looks a bit like Hall's condition (maybe I'm thinking in a completely wrong direction here). So I tried to construct some auxiliary, bipartite graph, which would have a matching because of: $|E(G[S])| ≤ k|S|$ and see how I can go from there. I got this idea from a proof I saw, of the fact that every regular graph of positive even degree has a $2$-factor.

Unfortunately I didn't even manage to come up with an interesting auxiliary bipartite graph, which would be helpful. Maybe someone can give me a little push in the right direction, or can tell me whether my approach is even the right one?

Many thanks for any help or suggestions!

Answer 1

Take the bipartite graph with one of the partitions being $E$ and the other being $k$ copies of the nodes $V$. Connect each edge to its extrema (that are $2k$). Your condition says that for any subset of edges $E'$ the connected nodes are at least $|E'|$.

By Hall's marriage theorem, you can connect each edge to a distinct node. When you regroup the copies of the nodes, you will have that each node is connected to at most $k$ edges, so you can set their directions as directed away from the connected node.