Order and Size of Graph do not determine Degrees of Vertices

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$