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.
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 = \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 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
- 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
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Entry: graph