The acquired-immunodeficiency syndrome has evolved into a major worldwide epidemic. Significant effort has been made in the development of antiviral therapies. A new strategy for vaccine and drug design that complements the existing cocktail therapy is to target entry of the human immunodeficiency virus (HIV). Such an approach provides the advantage of interfering with multiple intermediates in this multi-step process. The extraordinary conformational flexibility, glycosylation, and strain variations of viral glycoprotein gp120 cause general viral evasion of humoral immune response and thus complicate the development of an effective vaccine. Especially difficult to define are the conformation of gp120 before CD4 engagement as well as the relative orientations of the V1/V2 and V3 loops with respect to the inner and outer domains. In this study, we used Floppy Inclusion and Rigid Substructure Topography (FIRST), a program based on graph theory, to analyze the flexibility and rigidity of all known HIV-1 gp120 structures. A flexibility index is used to describe and compare the spatial distribution of protein flexibility and rigidity of these structures in isolation and in complex with CD4, CD4-mimics, and neutralizing antibodies. Using this flexibility analysis, we identified a universal rigid region (the alpha2 helix) as well as the consensus largest rigid cluster involving a beta-sheet located on the coreceptor binding face. Both of these regions may serve as stable targets for vaccine design and drug discovery. Detailed comparisons of the changes in flexibility based on strain variations, stabilizing mutations, binding features of CD4 mimics, and impact of b12 binding are reported.