Reference no: EM131163824

1. Show that if two graphs have the same degree sequence then they have the same number of vertices and the same number of edges. Find two non-isomorphic graphs with the degree sequence (2, 2, 2, 1, 1)

2. Find all simple graphs on 4 vertices, up to isomorphism.

3. Let G and G! be graphs. Suppose that f : V (G) → V (G!) is an isomorphism. Let x, y ∈ V (G). Use induction to show that that the distance between x and y in G is equal to the distance between f(x) and f(y) in G!

4. Let G be a connected graph with k vertices of odd degree, where k & 0. Show that the minimum number of trails with mutually distinct edges needed to cover every edge of G is k/2.

5. Show that the complete graph on n vertices has n(n - 1)/2 edges.