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


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.


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.


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

The edges are the elements of $E$.


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

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


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

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


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.


Arbitrary Example 1


Arbitrary Example 2


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.