0
$\begingroup$

Suppose that a connected graph $G$ has $11$ vertices and $53$ edges. Show that G is not Eulerian.

I can prove it for a simple graph by saying that the sum of degrees of all vertices can be maximum $100$ (max degree $10$ for each vertex) which corresponds to $50$ edges. But the given graph has $53$ edges.

How do I prove the same for a multigraph?

$\endgroup$
2
$\begingroup$

Two things: First, your argument for simple graphs is off. A simple graph on $11$ vertices can have up to $55$ edges (in general, a simple graph on $n$ vertices can have up to ${n\choose 2}$ edges).

Secondly, there do exist Eulerian multigraphs on 11 vertices with 53 edges: For example, take a cycle of length 11 (11 edges). Now between two consecutive vertices, place $42$ edges. Then each vertex has even degree (either $2$ or $44$) and so this graph is Eulerian.

$\endgroup$
0
$\begingroup$

If you take a complete graph on 11 nodes, it will have 55 edges, and every node will have degree 10. To construct a graph with 53 edges we must remove two edges. There are two cases to consider: either the two edges share a node or they don't.

Case 1: Call three of the nodes $A$, $B$, and $C$. Remove edges $AB$ and $BC$. Now $A$ and $C$ have degree 9, $B$ has degree 8 and all other nodes have degree 10. The graph remains connected, so there is an Eulerian path from $A$ to $C$ but there is no Eulerian cycle.

Case 2: Remove two disjoint edges $AB$ and $CD$ (where $D$ is a fourth node) Now there are four nodes of degree 9 so there is not even an Eulerian path.

In both cases there is no Eulerian cycle.

$\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.