For each of the following statements, say whether the statement is true or false. If true, prove

the statement (by giving an argument that would convince another student). If false, disprove the statement

(by giving a counterexample: an example that satisfies all the stated conditions but not the conclusion).

(i) If a directed graph or multigraph G has no isolated vertices and has a directed Euler circuit, then there

is a directed path in G from x to y for every two distinct vertices x, y in G.

(ii) If a directed graph or multigraph G has no isolated vertices and has a directed path from x to y for every

two distinct vertices x, y in G, then there is a directed Euler circuit in G.

(iii) A loop-free undirected graph G with n 2 vertices contains two distinct vertices having the same degree.

(iv) An undirected graph G = (V, E) with |V | = n and |E| = e has some vertex whose degree is at least 2e/n,

and some vertex whose degree is at most 2e/n.