Orientation of sparse graph
Task number: 4003
Let’s have a graph \(G=(V,E)\) such that for some \(k\in\mathbb N\) it holds: \(\forall H \subseteq G: |E(H)| \leq k \cdot |V(G)|\).
Show thet there exists an oriention of \(G\) such that \(\forall u \in V: \deg_{in} (u) \leq k\).
Hint
Adjust the incidence graph suitably.
Solution
We create a set system where sets are indexed by edges. For each edge \( e = (u, v) \) create a set from \( 2k \) elements \( M_e = \{u_1,…, u_k, v_1,…, v_k \} \) , i.e. replace each vertex with its \( k \) copies.
In this set system, the Hall condition is satisfied, so each edge of \( e \) can be represented by one of the \( k \) copies of \( u_i \) of the vertex \( u \) . In this case, we will direct the edge \( e \) towards \( u \). Since \( k \) copies were created from \( u \), its copies can represent at most \( k \) edges and therefore \(\deg_{in} (u) \leq k \)
