(i) Let $G$ be a connected graph of order $n \geq 3$ such that for any two vertices $x$ and $y$,

$$d(x)+d(y) \geq k$$

Show that if $k<n$ then $G$ has a path of length $k$, and if $k=n$ then $G$ is Hamiltonian.

(ii) State and prove Hall's theorem.

[If you use any form of Menger's theorem, you must state it clearly.]

Let $G$ be a graph with directed edges. For $S \subset V(G)$, let

$$\Gamma_{+}(S)=\{y \in V(G): x y \in E(G) \text { for some } x \in S\}$$

Find a necessary and sufficient condition, in terms of the sizes of the sets $\Gamma_{+}(S)$, for the existence of a set $F \subset E(G)$ such that at every vertex there is exactly one incoming edge and exactly one outgoing edge belonging to $F$.