User:Scshunt/Definition:Graph Incidence Function

Informal Definition

An graph incidence function is, intuitively, any function which is the incidence function for some graph.

Formal Definition

Let $V$ and $E$ be sets.

Let $\phi : V \times E \left\{{0, 1}\right\}$ be a function satisfying the following properties:

• For all $e \in E$, there exist exactly two $v \in V$ such that $\phi\left({v, e}\right) = 1$.
• For all distinct $v, w \in V$, there exists at most one $e \in E$ such that $\phi\left({v, e}\right) = \phi\left({w, e}\right)$.

Then $\phi$ is an graph incidence function.

Alternate Graph Definition

An incidence function $\phi$ defines a graph whose incidence function is isomorphic to $\phi$.

Conversely, any graph incidence function of a graph defines an incidence function on its vertex and edge sets.

Accordingly, a graph can equivalently be defined as a vertex set, an edge set, and an incidence function on those sets.