Definition:Graph (Graph Theory)

From ProofWiki
Jump to navigation Jump to search

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

Informal Definition

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

ExampleOfGraph.png


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 = \left({V, E}\right)$ be a graph.

The order of $G$ is the count of its vertices.


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

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