Incidence (graph)

In graph theory, a vertex is incident with an edge if the vertex is one of the two vertices the edge connects.

An incidence is a pair ${\displaystyle (u,e)}$ where ${\displaystyle u}$ is a vertex and ${\displaystyle e}$ is an edge incident with ${\displaystyle u}$. Two distinct incidences ${\displaystyle (u,e)}$ and ${\displaystyle (v,f)}$ are adjacent if and only if ${\displaystyle u=v}$, ${\displaystyle e=f}$, or the edge ${\displaystyle uv}$ equals ${\displaystyle e}$ or ${\displaystyle f}$.

A graph can be formally defined as an ordered triple ${\displaystyle (V,E,\psi )}$, where ${\displaystyle V}$ is the set of vertices, ${\displaystyle E}$ is the set of edges, and ${\displaystyle \psi }$ is an incidence function (or incidence mapping) that maps each edge to a pair of vertices. For an edge ${\displaystyle e\in E}$, if ${\displaystyle \psi (e)=(u,v)}$, then ${\displaystyle u}$ and ${\displaystyle v}$ are called the end-vertices (or endpoints) of the edge ${\displaystyle e}$, and the edge ${\displaystyle e}$ is said to be incident with vertices ${\displaystyle u}$ and ${\displaystyle v}$.

A graph can also be specified as an incidence structure ${\displaystyle S=(P,B,I)}$, where ${\displaystyle P}$ is a set of "points" (the vertices), ${\displaystyle B}$ is a set of "blocks" (the edges), and ${\displaystyle I}$ is the incidence relation between them.