I want to know if there exist a algorithm to efficiently compute the number of odd vertex in an undirected graph?
A graph vertex in a graph is said to be an odd vertex if its vertex degree is odd, degree of a graph vertex v of a graph G is the number of graph edges which touch vertex v.
This post conclusion seems to be that this is #P-hard but this doesn't seem that hard to me but I don't have any direct argument against it ,that's why I want to know if there exist a reduction from this problem to some #P-complete problem or is it polynomially solvable?
What I didn't understand from linked post is why counting odd vertex is related to counting number of satisfiable instance of SAT.
Also counting the number of odd vertex seems to be solvable in linear time ,all we'd have to do is check each vertex to see if they have a odd degree if yes add 1 to the odd_vertex_number variable ,this way we can solve it in linear time ,that's why I can't understand why this is #P-hard?