Definition:Graph (Graph Theory)/Order

This page is about the order of a graph. For other uses, see order.

Definition

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

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

That is, the order of $G$ is $\card V$.

Examples

Arbitrary Order $4$ Graph

Let $G = \struct {V, E}$ be the graph defined as:

$V = \set {v_1, v_2, v_3, v_4}$

$E = \set {\set {\tuple {v_1, v_2}, \tuple {v_2, v_1} }, \set {\tuple {v_1, v_3}, \tuple {v_3, v_1} }, \set {\tuple {v_2, v_3}, \tuple {v_3, v_2} }, \set {\tuple {v_3, v_4}, \tuple {v_4, v_3} } }$

Then the order of $G$ is the cardinality of $V$:

$\card V = 4$

Also see

• Definition:Null Graph: the graph of order zero

• Definition:Size of Graph

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.3$: Graphs
• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): order: 10. (of a graph)
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): order: 10. (of a graph)