Order and Size of Graph do not determine Degrees of Vertices
Jump to navigation
Jump to search
Theorem
Let $G = \struct {V, E}$ be a simple graph.
Let both the order $\card V$ and size $\card E$ of $G$ be given.
Then it is not always possible to determine the degrees of each of the vertices of $G$.
Proof
The following $2$ simple graphs both have order $4$ and size $4$:
But:
- the graph on the left has vertices with degrees $1, 2, 2, 3$
- the graph on the right has vertices with degrees $2, 2, 2, 2$.
$\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 $6$