• A Graph is Sparse if random vertex pairs are not likely to share an edge
  • Linked List is sparse