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

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!

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.