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)
Best Answer
Use the following theorem: If a graph has any vertices of odd degree, then it cannot have an Euler Circut. Let's examine the degree of the vertices. As you correctly noticed a graph on a vertices with 25 edges is $K_8$ minus $3$ edges. Also, as you noted, if you remove edges you decrease the vertex degree, however, this can happen in multiple ways
1) You remove $3$ edges such that $6$ different vertices are affected, thereby reducing the degree from $7$ to $6$ for $6$ of $8$ vertices
2) You remove $3$ edges such that $4$ different vertices are affected, thereby reducing the degree from $7$ to $5$ for at least $1$ of those vertices.
In either of those cases we still have at least $1$ vertex of odd degree so $25$ cannot have an Eulerian circuit.
What about $24$? Well we can do something special now by removing $4$ edges, we can decrease the degree of every vertex by $1$ meaning that all vertices now have degree $6$ and we know If a graph is connected and every vertex has even degree, then it has at least one Euler circuit