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 Answers 2

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$

You must log in to answer this question.

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