Let G be a graph and let V(G) be the vertex set of G. Define the neighborhood complex N(G) as the simplicial complex whose simplices are those subsets of V(G) which have a common neighbor.