Graph

Topics: Graph Theory

---

A graph $G=\{V,E\}$ is a mathematical structure that consists of two finite sets $V$ and $E$.

• The elements of $V$ are called vertices or nodes.
• The elements of $E$ are called edges.
• The set of vertices must be a non-empty set, but the set of lines can empty.

We can use graphs to represent the relationship between different elements. A digraph is an example of a graph.

Graphs can be of several types (🗺).

Order and Cardinality

The order of $G$ is the cardinality of $V$, while the size of $G$ is the cardinality of $E$.

Example

The following is a graph with vertices $A,B,C,D$ and edges $f,g,h,i$:

Degree Sequence §

We denote the minimum vertex degree in a graph with ${\delta }_{min}$ or $\delta$, and the maximum with ${\delta }_{max}$ or $\Delta$.

We can represent graphs with the non-increasing sequence of its vertices’ degrees. Do note that two graphs with the same sequence aren’t necessarily isomorphic.