# Definition:Graph (Graph Theory)

*This page is about graph in the context of graph theory. For other uses, see Definition:Graph.*

## Contents

## Informal Definition

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

## Formal Definition

A **graph** is an ordered pair $G = \left({V, E}\right)$ such that:

- $V$ is a set, called the vertex set;
- $E$ is a set of 2-element subsets of $V$, called the edge set.

That is: $E \subseteq \left\{{\left\{{u, v}\right\}: u, v \in V}\right\}$.

$E$ can also be described as an antireflexive, symmetric relation on $V$.

### 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 **$\left({p, q}\right)$-graph**.

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

## Also see

- Definition:Null Graph: A
**graph**whose vertex set is empty.

- Definition:Multigraph: A
**graph**which may have more than one edge between a given pair of vertices; - Definition:Loop-Graph: A
**graph**which allows an edge to start and end at the same vertex. Such an edge is called a loop. - Definition:Directed Graph or Definition:Digraph: A
**graph**in which the edges are ordered pairs of vertices.

A **graph** which is not a multigraph nor a loop-graph nor a directed graph can be called a simple graph if this clarification is necessary.

## 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.

## Sources

- 1992: George F. Simmons:
*Calculus Gems*... (previous) ... (next): Chapter $\text {A}.21$: Euler ($\text {1707}$ – $\text {1783}$) - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**graph**