# Prove that graph isn't Eulerian

Let $$G$$ be a regular graph with even number of vertices and odd number of edges. Show that $$G$$ isnt an Eulerian graph.

I'm not sure if my solution is correct/misses something:

$$|V(G)| = 2k%$$ and $$|E(G)| = \frac{l \cdot 2k}{2} = k \cdot l$$, where $$l$$ is the degree of every vertice. If $$E$$ is odd then both $$k$$ and $$l$$ must be odd, so if $$l$$ is odd then the graph isn't Eulerian. What happens if the graph isn't regular, can I somehow explain why the graph could be Eulerian (other than showing an example?)

• I don't see a problem with your proof. I also don't see a better way to show that a (non-regular) graph of this kind can be Eulerian, than by providing an example. Do you have a good example in mind? Oct 23, 2022 at 23:58
• Well, take a graph with degree sequence $4,4,4,2,2,2$ as specified in one of the answers below. It has an even number of vertices and every vertex has even degree. How any edges though? In particular, is the number of edges even or odd.
– Mike
Oct 24, 2022 at 0:07
• Even though, if a graph has an even number of vertices, and odd number of edges, and in addition is regular, then as you have shown, the degree of each vertex must be odd--and the number of vertices cannot be a multiple of $4$ [even though it is a multiple of $2$].
– Mike
Oct 24, 2022 at 0:18
• Not relevant to the question, but perhaps worth pointing out explicitly: the singular of "vertices" is "vertex". Oct 24, 2022 at 7:58

See the picture for an example.

For an example, take a hexagon $$ABCDEF$$ with an inscribed triangle $$ACE$$.

ETA: It is not clear on whether or not the reader is insisting that the graph $$H=(V,E)$$, besides satisfying $$|V|$$ even and $$|E|$$ odd, is regular.

If $$H$$ is a regular graph with an even number of vertices and an odd number of edges, then $$H$$ is not Eulerian. Indeed, let $$d$$ be the degree of every vertex in $$H$$. Then the number $$|E|$$ of edges in $$H$$ satisfies $$|E|=\frac{d|V|}{2}$$; for $$|E|$$ to be odd with $$|V|$$ even, it follows that $$d$$ must be odd, and $$|V|$$ must not be a multiple of $$4$$. This was already noted in the OP and comments.

This is not true however, if the condition that $$H$$ is regular is removed.There is, in particular, a graph $$H$$ on an even number of vertices and with a odd number of edges [but not regular] that is Eulerian. In fact, there is a graph $$H$$ $$8$$ vertices where $$7$$ of the vertices have degree $$4$$ and the $$1$$ remaining vertex has degree $$2$$, and has $$(7 \times 4 +2)/2 = 15$$ edges [so $$8$$ vertices and $$15$$ edges total]. As every vertex has even degree in $$H$$, this graph $$H$$ is Eulerian.

To construct $$H$$, first let $$H'$$ be a complete bipartite graph on $$7$$ vertices, where one side $$V_1$$ has $$4$$ vertices and the other side $$V_2$$ has $$3$$ vertices [so $$H'$$ has exactly $$4+3=7$$ vertices]. Then every vertex on $$V_1$$ has degree exactly $$3$$ in $$H'$$ and every vertex in $$V_2$$ has degree exactly $$4$$ vertices. Then from $$H'$$ construct $$H$$ as follows:

1. First, put an edge between a pair of vertices in $$V_1$$. So now in $$V_1$$ there are $$2$$ vertices $$u_1$$ and $$u_2$$ of degree $$4$$ and $$2$$ vertices of degree $$3$$ in this graph, and every vertex in $$V_2$$ still has degree exactly $$4$$.

2. Now add an additional vertex $$v$$, and the edges $$u_1v$$ and $$u_2v$$. The resulting graph is $$H$$. Every vertex in $$V_1$$ has degree exactly $$4$$, and so does every vertex in $$V_2$$. The remaining vertex $$v$$ has degree $$2$$. The number of edges in $$H$$ is $$15$$.

• That's not a regular graph. Oct 24, 2022 at 17:50