# Definition:Graph (Graph Theory)

## Definition

A graph is intuitively defined as a pair consisting of a set of vertices and a set of edges.

### Vertex

Let $G = \struct {V, E}$ be a graph.

The vertices (singular: vertex) are the elements of $V$.

Informally, the vertices are the points that are connected by the edges.

In the above, the vertices (singular: vertex) are the points $A, B, C, D, E, F, G$ which are marked as dots.

### Edge

Let $G = \struct {V, E}$ be a graph.

The edges are the elements of $E$.

In the above, the edges are $AB, AE, BE, CD, CE, CF, DE, DF, FG$.

## Order

Let $G = \struct {V, E}$ be a graph.

The order of $G$ is the cardinality of its vertex set.

## Size

Let $G = \struct {V, E}$ be a graph.

The size of $G$ is the count of its edges.

## Notation

Let $G$ be a graph whose order is $p$ and whose size is $q$.

Then $G$ can be referred to as a $\tuple {p, q}$-graph.

A wider category: a graph whose order is $n$ can be referred to as an $n$-graph.

## Also see

• Results about graphs can be found here.

## Also defined as

Many treatments of this subject require that $V$ is non-empty, and so do not recognise the concept of a null graph.