Canonical: https://knowlpedia.com/discrete-structures/graph-vertex-edge/

# Graph: vertices and edges

Defines vertices and edges in a graph, along with incidence and adjacency.

A **(simple, undirected) graph** is an [ordered pair](https://knowlpedia.com/shared-foundations/ordered-pair/) \(G=(V,E)\) where:

- \(V\) is a [set](https://knowlpedia.com/shared-foundations/set/) of **vertices** (or **nodes**).
- \(E\) is a set of **edges**, where each edge is a 2-element subset \(\{u,v\}\subseteq V\).

If \(\{u,v\}\in E\), then:

- \(u\) and \(v\) are the **endpoints** of the edge,
- \(u\) and \(v\) are **adjacent** (neighbors), and
- the edge is **incident** to each of its endpoints.

## Remarks

**Common notation.** In a simple undirected graph, the edge \(\{u,v\}\) is often written as \(uv\).

The [degree](https://knowlpedia.com/discrete-structures/vertex-degree/) of a vertex counts its neighbors.

**Variants.** Depending on context, one may also allow:
- **Directed edges** \((u,v)\) (a directed graph),
- **loops** \(\{u,u\}\), and/or
- **multiple edges** between the same pair of vertices (a multigraph).

Unless stated otherwise, “graph” typically means **simple, undirected**.

A graph is called [finite-graph](https://knowlpedia.com/discrete-structures/finite-graph/) if it has finitely many vertices (and hence finitely many edges in the simple case).
