Inter-residue proximity constraints obtained in such experiments as cross-linking/mass spectrometry are important sources of information for protein structure determination. A central question in structure determination using these constraints is, What is the minimal number of inter-residue constraints needed to determine the fold of a protein? It is also unknown how the different structural aspects of constraints differentiate their ability in determining the native fold and whether there is a rational strategy for selecting constraints that feature higher fidelity in structure determination. To shed light on these questions, we study the fidelity of protein fold determination using theoretical inter-residue proximity constraints derived from protein native structures and the effect of various subsets of such constraints on fold determination. We show that approximately 70% randomly selected constraints are sufficient for determining the fold of a domain (with an average root-mean-square deviation of <= 3.4 angstrom from their native structures). We find that random constraint selection often outperforms the rational strategy that predominantly favors the constraints representing global structural features. To uncover a strategy for constraint selection for the optimal structure determination, we study the role of the topological properties of these constraints. Interestingly, we do not observe any correlation between various simple topological properties of the selected constraints, emphasizing different global and local structural features, and the performance of these constraints, suggesting that accurate protein structure determination relies on a composite of global and local structural information.