Maximum Degree of Vertex in Simple Graph/Examples/Impossible Order 5 Graph

Examples of Degrees of Vertices

There exists no simple graph whose vertices have degrees $2, 3, 4, 4, 5$.

Proof

Aiming for a contradiction, suppose there exists a simple graph $G = \struct {V, E}$ with $5$ vertices whose degrees are $2, 3, 4, 4, 5$.

One of the vertices of $G$ has degree $5$.

This contradicts Maximum Degree of Vertex in Simple Graph, which states that no vertex of $G$ can have a degree higher than $4$.

$\blacksquare$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex: Problem $3$