3
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

the solution is at least K-1. If there is that cycle, denote as "d" one of the vertices in that cycle. Now for every a and b in V, there must be a path a->d->b. If that path has even vertices is ok, else you make one cycle resulting in an odd+odd=even number of vertices. Note that that cycle is always in the same connected component.

But this doesn't prove the fact that if there isn't that cycle, the solution is K.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.