Protein-protein interaction networks (PINs) are structured by means of a few highly connected proteins linked to a large number of less-connected ones. Essential proteins have been found to be more abundant among these highly connected proteins. Here we demonstrate that the likelihood that removal of a protein in a PIN will prove lethal to yeast correlates with the lack of bipartivity of the protein. A protein is bipartite if it can be partitioned in such a way that there are two groups of proteins with intergroup, but not intragroup, interactions. The abundance of essential proteins found among the least bipartite proteins clearly exceeds that found among the most connected ones. For instance, among the top 50 proteins ranked by their lack of bipartivity 62% are essential proteins. However, this percentage is only 38% for proteins ranked according to their number of interactions. Protein bipartivity also surpasses another 5 measures of protein centrality in yeast PIN in identifying essential proteins and doubles the number of essential proteins selected at random. We propose a possible mechanism for the evolution of essential proteins in yeast PIN based on the duplication-divergence scheme. We conclude that a replica protein evolving from a nonbipartite target will also be nonbipartite with high probability. Consequently, these new replicas evolving from nonbipartite (essential) targets will with high probability be essential.