Maximum Degree of Vertex in Simple Graph
Jump to navigation
Jump to search
Theorem
Let $G = \struct {V, E}$ be a simple graph.
Let $\card V$ denote the order of $G$.
Then no vertex of $G$ has a degree higher than $\card V - 1$.
Proof
By definition, a simple graph has no loops or multiple edges.
So a vertex can be incident to only as many edges that will join it to all the other vertices once each.
There are $\card V - 1$ other vertices.
Hence the result.
$\blacksquare$
Examples
Impossible Order $5$ Graph
There exists no simple graph whose vertices have degrees $2, 3, 4, 4, 5$.