# Is it possible to know if such path in a graph exists?

Given a directed graph $G$, a node $n \in G$, is it possible (besides bruteforcing for all possible solutions) to know if there exists a path starting from the node $n$ and such that we visit each node of the graph an odd number of times?

There are no other constraints except the starting point and the fact that I have to visit all nodes of the graph respecting the previous condition.

EDIT I'll make an example. Let's consider the graph in this picture: and assuming I want to start with the node 'a', there is no way to visit the graph passing through each node exactly 1 time (the only path is "a, c, a, b" passing through 'a' 2 times). If the starting node is 'c', instead, it's possible to do "c, a, b" and that satisfies the conditions.

Now obviously the graph isn't fully connected, but also changing the starting point can make things possible.

EDIT 2 I now realize the term "path" could be misleading. I just need to pass through each node an odd number of times.

To determine the connectedness (connectivity?) of a graph, you should first construct an adjacency matrix $A$. Then find a new matrix $M$ which is the sum of the integer powers of $A$ up to and including the number of largest possible path length (if you know it) or simply the number of nodes/vertices $n$: $$M = \sum\limits_{i=1}^{n} A^i = A + A^2 + A^3 + \cdots + A^n$$ If the matrix $M$ contains any entries that are $0$'s, the graph is not connected and therefore not every vertex has a path to every other vertex. Equivalently, if all the entries of $M$ are non-zero, then the original graph is connected.
Based on your profile name, I can guess you're a fan of computational efficiency. There are ways to compute larger powers of A (a.k.a. very large number of vertices) by keeping track of the power of A with an exponent that is a power of 2. Examples: $$A^3=A^2A \\ A^6=A^4A^2\\A^{27}=A^{16}A^8A^2A^1$$ I recommend looking into the binary representation of your original exponent to find the powers of the corresponding "powers of 2" adjacency matrices. Then add them all up and see if the resulting matrix contains any zeros! If not, it is fully connected.