1
$\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$
3
  • $\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, 2015 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, 2015 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, 2015 at 14:40

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .