"evenly connected" graph

An undirected graph $G=(V,E)$ is "evenly connected" if for every $v\in V$ there's a (not neceserally simple!) path to all the other vertices, with even number of edges.

Let $G=(V,E)$ be an undirected graph where $3\leq |V|, 2\leq |E|$.
We want the minimal number of edges we need to add to $G$ in order to make the graph evenly connected

Proposed algorithm:

• Find the number of connected components. Lets denote it as $K$.

• Check if there's a cycle with an odd amount of edges in $G$.

If there is, return $K-1$; else, return $K$.

The algorithm is true, but I can't figure out why.
It was asked as part of a multiple choice question, so it's something you need to "see" is true, but I don't really see why.

For now assume that the graph is connected. If the graph contains an odd cycle $C$, then you can build an even walk between any two vertices as follows: Let $v$ the first vertex of $C$. Then for any two vertices $u, w$.
Let $P$ be an arbitrary path from $u$ to $v$ and $P'$ be a path from $v$ to $w$. Let $W$ be the walk resulting from the concatenation of $P$ and $P'$, and let $W'$ be the walk resulting from concatenating $P,C$ and $P'$. Then either $W$ or $W'$ is even.

On the other hand, if $G$ does not admit an odd cycle, then $G$ is bipartite, and there exist only odd walks between the vertices of one side, and the vertices of the other. We can fix this problem by adding a single edge to any path of length two creating a triangle in $G$.

Finally, if $G$ is not connected, we can make it connected by adding $K-1$ edges connecting different components arbitrarily. Since we cannot introduce cycles by adding a single edge between two components, we still have to add one more edge if $G$ does not contain an odd cycle.

StackExchange Computer Science Q#161370, answer score: 3