MathDB

For a subset

S

of vertices of graph

G

, let

\Lambda(S)

be the subset of all edges of

G

such that at least one of their ends is in

S

. Suppose that

G

is a graph with

m

edges. Let

d^*: V(G)\longrightarrow\mathbb N\cup\{0\}

be a function such that a) \sum_{u}d^*(u)\equal{}m. b) For each subset

S

V(G)

\sum_{u\in S}d^*(u)\leq|\Lambda(S)|

Prove that we can give directions to edges of

G

such that for each edge

e

, d^\plus{}(e)\equal{}d^*(e).

Problem Statement