There are two ways to formalize that problem.
If we are interested in finite graphs, we would define the problem to be a set of some triples of the form $(G, x, y)$ where $G$ is a (description of a) finite graph and $x, y$ are vertices in $G$. By picking some effective coding system, we can view each of these triples as a string or as a single natural number. The "problem" would then be defined formally as the set of triples $(G, x, y)$ such that there is a path from $x$ to $y$. This problem is decidable - there is an algorithm to tell whether a triple is in the set - but the question would be what subrecursive complexity class the problem lies in.
If we are interested in infinite graphs, we do something slightly different. For a fixed infinite (countable) graph $G$ there is a problem $P_G$ consisting of all pairs $(x,y)$ of vertices of $G$ such that there is a path from $x$ to $y$. For some graphs this problem is decidable, and for some it is not; in general we would be interested in how uncomputable the problem $P_G$ is in terms of the level of uncomputability of $G$ itself.
Both of these descriptions are correct on the large scale but leave out some details, which would be covered in depth in a book on computability.