I want to show that for any graph $G$, there exists at least 1 vertex with an odd number of edges.
${\textbf{Additional Requirement}}$:
One of the vertices must have an edge to a vertex "outside" $G$. Think of that "outside" edge being a way in to a city ($G$), or door to a house ($G$).
So, for instance of a house: The vertices are rooms and the edges are doors. There exists only one entrance (a door) in to the house.
I've thought about the case for a complete graph,
\begin{equation}
\begin{aligned}
n&=2k+1, k \in \mathbb{Z}^+_0 \\
K_n &\Rightarrow deg(n-1) \\
&\Rightarrow deg(2k)\\
\end{aligned}
\end{equation}
then we simply add the "outside" edge and vertex to one of the $n$ vertices, giving us a graph with one vertex having an odd number of edges.
But that does not apply to "any graph".
I'd really appreciate some guidance and help!
Thanks!
Best Answer
Let $\mathcal{G}$ be a graph with $n$ vertices, and $\mathcal{G'}$ be a subgraph with $n-1$ vertices such that the vertex in $\mathcal{G}\setminus\mathcal{G'}$ (the "outside") is connected to exactly one vertex in $\mathcal{G'}$. We want to show that there must be a vertex in $\mathcal{G'}$ with odd degree.
Let $v_0$ be the vertex which is connected to "the outside" by an edge, and for a contradiction suppose all $v \in \mathcal{G}$ have even degree.
This requires $v_0$ to have an odd number of connections in $\mathcal{G'}$, and all other vertices in $\mathcal{G'}$ to have even number of connections in $\mathcal{G'}$. This means the sum of degrees in $\mathcal{G}$ is odd - which is not possible since the total number of edges (an integer) is the sum of degrees divided by two.
So there must be at least one vertex in $\mathcal{G'}$ with odd degree.