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

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.

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.

Examples

Arbitrary Example 1

Arbitrary Example 2

Also see

• Definition:Simple Graph: a graph which:
  • has no more than one edge between a given pair of vertices
  • in which the edges start and end on different vertices.

• 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 (Graph Theory)

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

• 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 in the context of graph theory can be found here.

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
• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): graph: 2.
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): graph: 2.
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): graph