I wrote this proof for simple graphs. Any feedback is appreciated.
Theorem: A connected graph has an Euler circuit $\iff$ every vertex has even degree.
Proof:
$P \implies Q$, we want to show that if a connected graph $G$ has an Euler circuit, then all $v \in V(G)$ have even degree.
An Euler circuit is a closed walk such that every edge in a connected graph $G$ is traversed exactly once. We define $w = v_0, v_1, v_2, … v_k$, such that $v_0 = v_k$, to be that Euler circuit in $G$ of length $k$.
We assume $|V(G)| > 0$.
Case 1, $0 < i < k$: Since all edges in $w$ will be traversed, but no edge can be traversed more than once, we reach $v_i$ via one edge $\{v_{i-1}, v_i\}$ and have to leave via another untraversed edge $\{v_i, v_{i+1}\}$, so $deg(v_i) = 2n$, where $n$ is equal to the number of times $v_i$ appears in $w$, for $0 < i < k$.
Case 2, $i \in {0, k}$: At the beginning of $w$, we traverse any edge incident to $v_0$, that is $\{v_0, v_1\}$. By definition of an Eulerian circuit, we also have to conclude the walk at the same vertex where we started, hence we reach $v_0 = v_k$ again via a different, $k$-th edge $\{v_{k-1}, v_k\}$. Every $n$ times we pass $v_0 = v_k$ before concluding the walk, Case 1 applies, hence $deg(v_0) = deg(v_k) = 2 + 2n$, which is even.
$Q \implies P$, we want to show the other direction, that is if all $v \in V(G)$ have even degree, then a connected graph $G$ has an Euler circuit.
Proposition $P(n)$: If $G$ is a connected graph with $n$ edges and all $v \in V(G)$ have even degree, then $G$ has an Euler circuit. We proceed by induction on $n$.
Base case $P(0)$: A connected graph without any edges has only one vertex $v$ with $deg(v) = 0$, therefore $P(0)$ is true.
For purpose of induction, we assume $P(n)$ is true.
Inductive step, $P(n + 1)$: Assume $G$ has $n+1$ edges. Since all $v \in V(G)$ have even degree, we know $G$ can't be a tree, so we can find a cycle $c = u_0, u_1, …, u_i, …, u_k$ of length $k$ in $G$.
If $k = |E(G)|$, we found an Eulerian circuit that visits all edges exactly once and are done.
Otherwise, remove all edges in $c$ from $G$. The resulting subgraph $G'$ might contain $s$ connected components $G'_j$ for $0 \leq j < s$.
We know that all vertices in $c$ have even degree, so any vertex in $G'_{j}$ that was adjacent to a vertex in $c$ will have an even number of edges removed, therefore the parity of all $v \in G'$ remains even. the Also, all $G'_j$ will have at most $n$ edges.
Therefore we can assume $P(n)$ for all $G'_j$, that means we can find a Eulerian walk $w_j$ in each $G'_j$.
Now reinsert the edges from $c$ into $G'$, reconstructing $G$. We walk all vertices in $c$, starting at any vertex $u \in c$. When we reach a vertex $u_i$ in $c$ for the first time and $u_i$ was part of a $G'_j$, we branch into $w_j$, follow that Eulerian walk $w_j$ until its end and continue to $u_{i+1}$. We do this for all $G'_j$ until we reach $u_k$.
This will form an Eulerian walk that visits all edges in $G$ exactly once.
I found the last part, where the cycle is re-inserted into the graph again quite hairy to describe properly, but leaving out superfluous details.
Best Answer
There are two parts of your proof that I would consider incorrect, leaving out important details (which I'm sure you were aware of, but didn't write down):
In the $P \implies Q$ direction, Case 2, you only show that $\deg v_0 \ge 2$, which doesn't mean that it's even: $17 \ge 2$ and $17$ is odd. What you really want to argue here is that we use edges out of $v_0=v_k$ once at the very beginning, once at the very end, and twice every time it appears in the middle of the walk (this part is identical to Case 1), for a total of $2n+2$ edges, which is even.
In the $Q \implies P$ direction, when you write
this will not generally produce an Eulerian tour at the end. The closed walk $w_j$ might visit $u_i$ many times, and if you continue along $c$ the first time you return to $u_i$, you might miss out on many edges in $G_j'$. Instead, what you should do in this step is walk the entirety of the closed walk $w_j$, starting at $u_i$ and therefore ending at $u_i$, and then continue along $c$ to $u_{i+1}$.
Aside from that, I just have a couple of comments on clarity.
First, when you begin your induction
you're not really using the right form for $P(n)$: you haven't made it a statement that depends on $n$. What you really want to define $P(n)$ to be is the proposition that "If $G$ is a connected graph with $n$ edges and all $v \in V(G)$ have even degree, then $G$ has an Euler circuit." (This also avoids the problem that, within the statement, you talk about $V(G)$ before you've said what $G$ is.)
Second, I'm not sure $P(3)$ is the right base case. I'd actually go with $P(0)$ (a graph with one vertex and no edges is connected, all vertices have even degree, and it has a trivial closed walk) because in your induction step, when you delete the cycle $c$, you may well end up with plenty of components that $P(0)$ should apply to. (And if we have $P(0)$, we can use it to prove $P(3)$: remove the cycle of length 3, and you have three components with $0$ edges.)
Third, a minor nitpick: when you're combining all the cycles together, you should only take the closed walk of $G_j'$ the first time you reach a vertex $u_i \in c$ that is a part of $G_j'$. (This is obvious if you know what you're doing, but it needs to be said if you want to describe a correct algorithm.)
But overall, well done! This is a complicated proof to write, with lots of fiddly details (which I didn't fully appreciate myself before I had to teach a recitation on it last semester), and you did a good job hitting all the important points. Don't let the length of my comments make you think otherwise.