Es sei ${\displaystyle {}M}$ eine (endliche) Menge und ${\displaystyle {}V={\mathfrak {P}}\,(M)}$ die zugehörige Potenzmenge, die wir als Knotenmenge eines Graphen nehmen. Wir verbinden zwei Knoten, also zwei (verschiedene, um Schleifen zu vermeiden) Teilmengen ${\displaystyle {}S,T\subseteq M}$ genau dann durch eine Kante, wenn ${\displaystyle {}S\cap T\neq \emptyset }$ ist, wenn also die beiden Teilmengen nicht zueinander disjunkt sind. Man spricht vom Potenzmengengraphen.