Several application fields require finding Euclidean coordinates consistent with a set of distances. More precisely, given a simple undirected edge-weighted graph, we wish to find a realization in a Euclidean space so that adjacent vertices are placed at a distance which is equal to the corresponding edge weight. Realizations of a graph can be either flexible or rigid. In certain cases, rigidity can be seen as a property of the graph rather than the realization. In the last decade, several advances have been made in graph rigidity, but most of these, for applicative reasons, focus on graphs having a unique realization. In this paper we consider a particular type of weighted Henneberg graphs that model protein backbones and show that almost all of them give rise to sets of incongruent realizations whose cardinality is a power of two. © 2013 Elsevier B.V. All rights reserved.165 213232Barvinok, A., Problems of distance geometry and convex properties of quadratic maps (1995) Discrete and Computational Geometry, 13, pp. 189-202Berger, B., Kleinberg, J., Leighton, T., Reconstructing a three-dimensional model with arbitrary errors (1999) Journal of the ACM, 46 (2), pp. 212-235Biswas, P., Lian, T., Wang, T., Ye, Y., Semidefinite programming based algorithms for sensor network localization (2006) ACM Transactions on Sensor Networks, 2, pp. 188-220Blumenthal, L., (1953) Theory and Applications of Distance Geometry, , Oxford University Press OxfordBrady, T., Watt, C., On products of Euclidean reflections (2006) American Mathematical Monthly, 113, pp. 826-829Connelly, R., Generic global rigidity (2005) Discrete & Computational Geometry, 33, pp. 549-563Coope, I., Reliable computation of the points of intersection of n spheres in Rn (2000) The Australian and New Zealand Industrial and Applied Mathematics Journal, 42, pp. 461-C477Cremona, L., (1872) Le Figure Reciproche Nella Statica Grafica, , G. Bernardoni MilanoCrippen, G., Havel, T., (1988) Distance Geometry and Molecular Conformation, , Wiley New YorkDattorro, J., (2005) Convex Optimization and Euclidean Distance Geometry, , Meboo Palo AltoDong, Q., Wu, Z., A geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data (2003) Journal of Global Optimization, 26, pp. 321-333Eren, T., Goldenberg, D., Whiteley, W., Yang, Y., Morse, A., Anderson, B., Belhumeur, P., Rigidity, computation, and randomization in network localization (2004) IEEE Infocom Proceedings, pp. 2673-2684Graver, J., Rigidity matroids (1991) SIAM Journal on Discrete Mathematics, 4, pp. 355-368Graver, J., Servatius, B., Servatius, H., (1993) Combinatorial Rigidity, , American Mathematical SocietyGunther, H., (1995) NMR Spectroscopy: Basic Principles, Concepts, and Applications in Chemistry, , Wiley New YorkHendrickson, B., Conditions for unique graph realizations (1992) SIAM Journal on Computing, 21 (1), pp. 65-84Henneberg, L., (1911) Die Graphische Statik der Starren Systeme, , Teubner LeipzigJohn, A.L.-S., (2008) Geometric Constraint Systems with Applications in Cad and Biology, , Ph.D. Thesis, University of Massachusetts at AmherstKang, R., Müller, T., Sphere and dot product representations of graphs (2011) Proceedings of SCG11, pp. 308-314. , ACMLavor, C., Lee, J., John, A.L.-S., Liberti, L., Mucherino, A., Sviridenko, M., Discretization orders for distance geometry problems (2012) Optimization Letters, 6, pp. 783-796Lavor, C., Liberti, L., Maculan, N., (2006) The Discretizable Molecular Distance Geometry Problem, , Tech. Rep. q-bio/0608012, arXivLavor, C., Liberti, L., Maculan, N., Mucherino, A., The discretizable molecular distance geometry problem (2012) Computational Optimization and Applications, 52, pp. 115-146Lavor, C., Liberti, L., Mucherino, A., The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances (2011) Journal of Global Optimization, , http://dx.doi.org/10.1007/s10898-011-9799-6Lavor, C., Mucherino, A., Liberti, L., Maculan, N., An artificial backbone of hydrogens for finding the conformation of protein molecules (2009) Proceedings of the Computational Structural Bioinformatics Workshop, pp. 152-155. , IEEE Washington, DC, USALavor, C., Mucherino, A., Liberti, L., Maculan, N., Computing artificial backbones of hydrogen atoms in order to discover protein backbones (2009) Proceedings of the International Multiconference on Computer Science and Information Technology, pp. 751-756. , IEEE Mragowo, PolandLavor, C., Mucherino, A., Liberti, L., Maculan, N., Discrete approaches for solving molecular distance geometry problems using NMR data (2010) International Journal of Computational Bioscience, 1, pp. 88-94Lavor, C., Mucherino, A., Liberti, L., Maculan, N., On the computation of protein backbones by using artificial backbones of hydrogens (2011) Journal of Global Optimization, 50, pp. 329-344Liberti, L., Lavor, C., Maculan, N., A branch-and-prune algorithm for the molecular distance geometry problem (2008) International Transactions in Operational Research, 15, pp. 1-17Liberti, L., Lavor, C., Mucherino, A., Maculan, N., Molecular distance geometry methods: From continuous to discrete (2010) International Transactions in Operational Research, 18, pp. 33-51Liberti, L., Masson, B., Lee, J., Lavor, C., Mucherino, A., On the number of solutions of the discretizable molecular distance geometry problem (2011) Combinatorial Optimization, Constraints and Applications, 6831 VOL., pp. 322-342. , COCOA11 LNCS Springer New YorkMenger, K., Untersuchungen über allgemeine Metrik (1928) Mathematische Annalen, 100, pp. 75-163Mucherino, A., Lavor, C., The branch and prune algorithm for the molecular distance geometry problem with inexact distances (2009) Proceedings of the International Conference on Computational Biology, 58 VOL., pp. 349-353. , World Academy of Science, Engineering and TechnologyMucherino, A., Lavor, C., Liberti, L., Exploiting symmetry properties of the discretizable molecular distance geometry problem (2012) Journal of Bioinformatics and Computational Biology, 10, p. 1242009. , (1-15)Mucherino, A., Lavor, C., Liberti, L., The discretizable distance geometry problem (2012) Optimization Letters, 6, pp. 1671-1686Mucherino, A., Lavor, C., Liberti, L., Maculan, N., On the definition of artificial backbones for the discretizable molecular distance geometry problem (2009) Mathematica Balkanica, 23, pp. 289-302Mucherino, A., Lavor, C., Liberti, L., Talbi, E.-G., A parallel version of the branch & prune algorithm for the molecular distance geometry problem (2010) ACS/IEEE International Conference on Computer Systems and Applications, pp. 1-6. , AICCSA10 IEEE Hammamet, TunisiaMucherino, A., Lavor, C., Liberti, L., Talbi, E.-G., On suitable parallel implementations of the branch & prune algorithm for distance geometry (2010) Proceedings of the Grid5000, , Spring School Lille, FranceMucherino, A., Liberti, L., Lavor, C., MD-jeep: An implementation of a branch-and-prune algorithm for distance geometry problems (2010) Mathematical Software, 6327 VOL., pp. 186-197. , K. Fukuda, J. van der Hoeven, M. Joswig, N. Takayama, LNCS Springer New YorkNilges, M., Macias, M., O'Donoghue, S., Oschkinat, H., Automated NOESY interpretation with ambiguous distance restraints: The refined NMR solution structure of the Pleckstrin homology domain from β-spectrin (1997) Journal of Molecular Biology, 269, pp. 408-422Saviotti, C., Nouvelles méthodes pour le calcul des travures réticulaires (1885) Appendix to L. Cremona, les Figures Réciproques en Statique Graphique, pp. 37-100. , Gauthier-Villars ParisSaviotti, C., (1888) La Statica Grafica: Lezioni, , U. Hoepli MilanoSaxe, J., Embeddability of weighted graphs in k-space is strongly NP-hard (1979) Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480-489Schlick, T., (2002) Molecular Modelling and Simulation: An Interdisciplinary Guide, , Springer New YorkSchoenberg, I., Remarks to Maurice Fréchet's article sur la définition axiomatique d'une classe d'espaces distanciés vectoriellement applicable sur l'espace de Hilbert (1935) Annals of Mathematics, 36 (3), pp. 724-732So, A.M.-C., Ye, Y., Theory of semidefinite programming for sensor network localization (2007) Mathematical Programming, Series B, 109, pp. 367-384Tay, T.-S., Whiteley, W., Generating isostatic frameworks (1985) Structural Topology, 11, pp. 21-69Whiteley, W., Infinitesimally rigid polyhedra. I. Statics of frameworks (1984) Transactions of the American Mathematical Society, 285 (2), pp. 431-465Whiteley, W., Infinitesimally rigid polyhedra. II: Modified spherical frameworks (1988) Transactions of the American Mathematical Society, 306 (1), pp. 115-139Zhu, Z., So, A.M.-C., Ye, Y., Universal rigidity and edge sparsification for sensor network localization (2010) SIAM Journal on Optimization, 20 (6), pp. 3059-3081