Proof - a vertex in a path has an even number of edges

Question

Given a simple undirected graph,

let's say we have a path of i edges that can repeat nodes but not edges

i.e. nodes may come up more than once in the path but not the edges.

NOTE : I never said this path has to contain all edges in the graph. So I'm not assuming a Eulerian circuit. Just an arbitrary path formed by a subset of the edge set of the graph that may have repeating vertices but not edges.

For a node in the path that is not an endpoint of the path (one that is in the "middle"), I think we can say that it is adjacent to an even number of edges in the path. Not adjacent to any edge in the graph, but those that belong to the path containing this node.

It seems very intuitive but I couldn't figure out a way to formally prove this. Any suggestions?

Answer 1

You can use the "Euler Path Theorem" directly. It is as following:

Let $G$ be a finite connected graph and $r$ be the number of vertices with odd degree (this means there are odd number of edges adjacent to that vertex). Then $G$ has an Euler path if and only if $r = 0$ or $r = 2$.

Now, in your question, we have a path already so we know that $r = 0$ or $r = 2$ by Euler Path Theorem. If $r = 0$, we are done because every vertex has the property you stated (and this is an Euler cycle). If $r = 2$, then these vertices of odd degrees are "starting vertex" and "terminal vertex" so vertices in middle have even degree. So the result follows.

---

from OP : look at the comment on the main post then look at this accepted answer

Answer 2

A connected graph $G$ has an Eulerian circuit if and only if every vertex has even degree. Your observation from the title follows immediately from this standard characterization.