Given an undirected graph G = hV, Ei, let the TWO-HOP-COUNT of a vertex v be the number of unique vertices that can be reached from v (not including itself) using at most 2 edges. Prove that the number of vertices in G with an odd TWO-HOP-COUNT is even. Hint: Try transforming G into a different graph G0 , in such a way that you can use the handshaking lemma on G0 .

3. Given an undirected graph G-V,B), let the TWO-HOP-COUNT of a vertex v be the number of unique vertices that can be reached from v (not including itself) using at most 2 edges. Prove that the number of vertices in G with an odd TWO-HOP-COUNT is even. Hint: Try transforming into a different graph G,, in such a way that you can use the handshaking lemma on G