We prove that with high probability a skip graph contains a *4*-regular
expander as a subgraph and estimate the quality of the expansion via simulations.
As a consequence, skip graphs contain a large connected component even after an
adversarial deletion of nodes. We show how the expansion property can be used to
sample a node in the skip graph in a highly efficient manner. We also show that
the expansion property can be used to load balance the skip graph quickly.
Finally, it is shown that the skip graph could serve as an unstructured P2P
system, making it a good candidate for a hybrid P2P system.