For this question, we will assume that all graphs have a vertex-set that is non-empty and finite, that is 1 |V | < . Recall that we let d(v) denote the degree of a vertex in an undirected graph and d_in(v) and d_out(v) the in-degree and out-degree of a vertex in a directed graph respectively. For this question, let n = n₁ + n₂ + . . . + n₉ denote the sum of all the digits of your student ID ( 215216930). State what your n is before answering the questions. If your n is even, set k = 0. If your n is odd, set k = 1. Also state what your k is before answering the questions.

For the following three statements, determine (and clearly state) whether they are true or not and prove your claim.

• If G = (V, E) is an undirected graph without self-loops with n vertices, then there can not exist two vertices v and v ^j in V with d(v) = k and d(v ^j) = n 1 k.
• If G = (V, E) is a directed graph without self-loops that is strongly connected then for every vertex v V , we have d_in(v) 1 and d_out(v) 1.
• If G = (V, E) is an undirected, connected graph without self-loops with n vertices, for which every vertex has an even degree, then, if we remove any edge from G, the graph is still connected.

2 + 2 + 2 points