Topics: Graph Theory

A graph is a mathematical structure that consists of two finite sets and .

  • The elements of are called vertices or nodes.
  • The elements of 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 is the cardinality of , while the size of is the cardinality of .

Degree Sequence

We denote the minimum vertex degree in a graph with or , and the maximum with or .

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.