Need some help with this problem:
Let $G$ be a graph with vertex set $V$. Let $A, B$ be sets of vertices from $V$ where:
$\ A\cap B = \emptyset $
$\ A\cup B =V $
And also: $v$ is a vertex from $A$ and $w$ is a vertex from $B$, $v$ and $w$ are connected with edge $e$, which is the only edge connecting between vertices from $A$ and $B$.
We need to prove:
$G$ has a vertex with an odd degree.
Thinking about proof by contradiction, but can't get it through the end.
First of all, notice something interesting - you can choose to focus on A or B, and completely disregard the other component. The reason for the theorem is the fact that you have the vertices v and w, that have an "extra" edge that isn't connected to anything in their corresponding components. So for the sake of the proof, let's focus on strictly A + the edge e connected to it (it's not technically a graph, but bare with me). Also, WLOG let's assume that A is a connected graph - it makes things easier and it doesn't change the result (this can be easily proven).
Let's assume that we don't have a vertex of an odd degree. This means every vertex is of an even degree. Now let's look at A without the edge e - we thus created a sub graph of G, who's vertices are all of an even degree, except v (which was connected to e), which now has an odd degree. There's a theorem that states the the sum of degrees in a graph is an even number, but on the other hand you've just created a graph where every vertex has an even degree except one, so the sum must be odd - and there's your contradiction.
I believe there are simpler proofs, but this is the one that comes to mind.