I am given an undirected connected graph of $N$ vertices and $M$ edges. I need to make this undirected graph directed by directing edges.I need to check if it's possible to make a directed graph such that indegree of all vertices of new directed graph is even.
I could only think that if the edges of graph is odd, it's impossible to make such directed graph. I worked on this problem, but couldn't think more.
Constraints :$- 1 \leq N \leq 10^5$ and $1 \leq M \leq 10^5$
Example :-
$N = 4$
$M = 4$
Edges are $(1,2), (1,3), (2,4)$ and $(3,4)$
Answer :- Possible
We can make a directed graph, $1\rightarrow2$, $1\rightarrow3$, $4\rightarrow2$ and $4\rightarrow 3$. Note that indegree of all vertices is even.
It remains to prove that if the number of edges is even then we can direct them providing in-degree of each vertex is even. Assume to the contrary, that there exists a direction of edges of the graph with minimal and non-zero number of vertices of odd in-degree. Since the sum of in-degrees of all vertices of the graph equals to the number of edges, which is even, there are at least two vertices $v$ and $u$ of odd in-degree each. Since the graph is connected, there is a (shortest) path from $v$ to $u$. When we redirect each edge of this path, we change the parity of in-degree of $v$ and $u$, but don’t change the parity of in-degree of all other vertices of the graph. Thus we decreased a number of vertices of odd in-degree, a contradiction.