I have an assignment for next week and I'm stuck with these two questions :
a) Let G be a simple graph on 8 vertices with exactly 25 edges. Can G be Eulerian? How about with 24 edges?
What I did : a) A graph on 8 vertices contains at most C(8,2)=28 edges. So G is a complete graph -3 edges. In a 8 complete graph, each of 8 vertices connect to 7 others. We must find a way to remove 3 vertices such that each 8 vertices has an even degree. It is not possible, even if we remove them from different pairs of vertices (we would still have a pair of vertices with an odd degree). So G cannot be Eulerian. If G has 24 edges, then G is a 8 complete graph -4 edges. If we remove an edge for every pair of vertices then every vertex would have an even degree. G can be Eulerian (24 w/ edges)