0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Why do you think there is vertex that has 2 of 3 removed edges? You can remove 3 edges on the complete graph of 8 vertices by only reducing each vertex degree by 1 right? $\endgroup$ – user2879934 Dec 3 '15 at 19:05
  • $\begingroup$ Please, post only one question in one post. Posting several questions in the same post is discouraged and such questions may be put on hold, see meta. $\endgroup$ – Martin Sleziak Dec 4 '15 at 14:38
  • $\begingroup$ Isn't the part b posted here. You should not post the same question twice. (So probably the best solution seems to be remove it from this question, since you have posted a separate question in the meantime.) $\endgroup$ – Martin Sleziak Dec 4 '15 at 14:40
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.