# Definition:Graph (Graph Theory)

*This page is about Graph in the context of Graph Theory. For other uses, see Graph.*

## Definition

A **graph** is intuitively defined as a pair consisting of a set of vertices and a set of edges each with a vertex at each end.

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

### Edge

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

The **edges** are the elements of $E$.

## 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 presented as

While it is commonplace to present a **graph** as a diagram consisting of dots connected by lines, some sources use circles for the vertices.

In that way, the labels for the vertices can be written neatly inside the circles.

## Examples

### Arbitrary Example 1

### Arbitrary Example 2

## Also see

- Definition:Simple Graph: a
**graph**which:

- 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

- Definition:Loop-Multigraph: A
**multigraph**which is allowed to have loops

- Definition:Directed Graph or Definition:Digraph: A
**graph**in which the edges are**ordered pairs**of vertices.

- Definition:Weighted Graph, where in addition the edges are each mapped to a number

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

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

## Sources

- 1979: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*... (previous) ... (next): Chapter $1$: Preliminaries: $1.2$ Graphs and Trees - 1992: George F. Simmons:
*Calculus Gems*... (previous) ... (next): Chapter $\text {A}.21$: Euler ($\text {1707}$ – $\text {1783}$) - 1992: David Wells:
*Curious and Interesting Puzzles*... (previous) ... (next): The Bridges of Königsberg - 1993: Richard J. Trudeau:
*Introduction to Graph Theory*... (previous) ... (next): $2$. Graphs: Graphs - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (next): $\S 2.3.4.1$: Free Trees - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**graph**