# "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:

1. Find the number of connected components. Lets denote it as $$K$$.
2. 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.