Data from real-world graphs often contains incomplete information, so we only observe subgraphs of these graphs. It is therefore desirable to understand how a typical subgraph relates to the underlying host graph.

We consider several interrelated problems involving both random trees in host graphs and random subgraphs obtained by taking edges of the host graph independently with probability p. In the second case, we study the emergence of the giant component. We also use the spectral gap to understand discrepancy and expansion properties of a random subgraph.

The Erdos-Renyi random graph is the special case of this where the host graph is the complete graph Kn. Additional applications include taking a contact graph as the host graph, and viewing random subgraphs as outbreaks of a disease.