---
tag: 2KM46K20DZ
kind: definition
name: Hypergraph
msc: [05C65]
defines: CH2JRZNX7V
uses: [0SJ3RX9TXA, 05Q6G4EH2G]
sources:
  - url: https://en.wikipedia.org/wiki/Hypergraph
---

## Definition

A hypergraph is a pair $H = (V, E)$ where $V$ is a [[set|0SJ3RX9TXA]] and $E$ is a [[family|05Q6G4EH2G]] of nonempty subsets of $V$.
The elements of $V$ are the vertices, and the members of $E$ are the hyperedges.
Let $k$ be a positive integer.
The hypergraph $H$ is $k$-uniform if each hyperedge has exactly $k$ elements.

## Remarks

Some authors allow repeated hyperedges or the empty hyperedge; others require $E$ to be a set.
A [[graph|0JD5C82QMB]] is the same thing as a $2$-uniform hypergraph without repeated edges.
Example: the [[Fano plane|QQ8GW1ASZM]], with the $7$ points as vertices and the $7$ lines as hyperedges, is a $3$-uniform hypergraph, since each line has $3$ points.
Non-example: $V = \set{1, 2, 3}$ with $E = \set{\set{1, 2}, \set{1, 2, 3}}$ is a hypergraph that is not $k$-uniform for any $k$, because its hyperedges have sizes $2$ and $3$.
Every hypergraph has an incidence matrix, with a row for each vertex and a column for each hyperedge.