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

Also defined as

Some treatments of graph theory require that the vertex set $V$ is non-empty, and so do not recognise the concept of a null graph.


Arbitrary Example 1


Arbitrary Example 2


Also see