E is a subset of { {a,b} | a,b in V and a ≠ b }.

If c in V, we define

Prove for any finite graph (V,E), with |V| > 1, thatE(c) = { {a,c} in E | a in V } V(c) = { a in V | {a,c} in E } d(c) = |E(c)| = |V(c)|

there exists a,b in V such that a ≠ b and d(a) = d(b).

Note:

V is the set of vertices of the graph. E is the set of edges of the graph. E(c) is the set of edges incident to vertex c. V(c) is the set of vertices adjacent to vertex c. d(c) is the degree of vertex c.