Does there always exist a reversible path between two states? For a reversible process it holds that $dS=\delta Q/T$. We thus get the fundamental relation of thermodynamics: $dS=dU/T+P/T dV$. The reasoning goes that because entropy is a state function, this relation holds even for irreversible processes because we can imagine that there is a reversible path between the two states. 
But how do we know there exists a reversible path between two given states?
 A: There is not just one reversible path between the initial and final thermodynamic equilibrium states of a system.  There are an infinite number of reversible paths, and they all give the exact same value for the change in entropy (as well as for the changes in the other thermodynamic functions).  The integral of $dq/T_{boundary}$ for all these paths is also greater than the corresponding integral for any irreversible path, where $T_{boundary}$ is the temperature at the boundary between the system and its surroundings.  This is known as the Clausius inequality.
A: you can always construct a Carnot cycle passing through any two states(on P-V graph).
Of course, Carnot cycle consists of 4 reversible paths. 
A: Just for the Comment;
Can I understand your statement quoted below is same as Box 1 below?

The reasoning goes that because entropy is a state function, this relation holds even for irreversible processes because we can imagine that there is a reversible path between the two states.

If so, all states shall be connectable by path, but it is not necessary that the path is reversible. In other words, as long as the path exists, everything is "ideal" in the sense of Box1.

Box1: 

*

*To define entropy (exchanged entropy; $S_e$), for any two states A and B, there is at least one "ideal" path between A and B.

*If $c_1$,$c_2$ are the "ideal" path between states A and B, then the following holds;
$$\int_{c_1} d{S_e} =\int_{c_2} d{S_e}$$

We call it a "quasi-static process" in which U, V ,N ,and ... are fixed at any stage of the reaction. This quasi-static process is used as a method to realize a path that can be considered as a curve in the (upper half of) Euclidean space.

*

*When we say that "entropy is a state quantity," that "entropy" is the exchange entropy.

*If the path were irreversible, then a new term, called generated entropy ($S_g$), will be generated. Clausius' inequality is not an equality if this generative entropy exists. Clausius' inequality is not an equality if this generative entropy exists.

Indeed as described here, $\delta Q $ is path-dependent. But, U, V, N and T are state quantities and your following equation is path-independent
$${dS}_{e}=dU/T+P/T dV +\mu/T dN$$
and if we define the new state quantity  $\delta Q_{rev}$, the   $\delta Q_{rev}$
$$\delta Q_{rev}=dU+P dV +\mu dN$$
then, the $\delta Q_{rev}/T$ is a closed form and having a potential.
So once we admit that $dS_e$ can be written as the above equation, whether the curve is of a reversible process or not, as long as we keep track of U, V, N, and T from time to time, we can "recover" the function $S_e$ even if we don't know the so-called $\delta Q$ itself, IMO.

But, it would be simpler to make it an axiom that there is something called "exchange entropy".　

A: 
The reasoning goes that because entropy is a state function, this relation ($dS=dU/T+P/TdV$) holds even for irreversible processes because ...

Well, this premise is wrong because an irreversible process goes through out-of-equilibrium states for which state variables such as T or P might not even be defined at the scale of the system, and such out-of-equilibrium states are out of the scope of (equilibrium) thermodynamics. That's actually why one needs to find reversible paths to be able to compute overall changes between two equilibrium* states.
* Indeed, for a reversible path to exist between two given states, all the intermediate states must be equilibrium states, and thus all the more so for the initial and final states considered.
Now, I admit that this does not answer the question of whether there always exists a reversible path between any two equilibrium states.
A: Its because the equation you mentioned Tds=dU + Pdv is now a point function and does not depend on the path. Although it is defined for a reversible process but its valid for all since it becomes a point function.
