Maximum Degree of Vertex in Simple Graph/Examples/Impossible Order 5 Graph
Jump to navigation
Jump to search
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$