# Degree of Vertex/Examples/Impossible Order 4 Graph

Jump to navigation
Jump to search

## Examples of Degrees of Vertices

There exists no simple graph whose vertices have degrees $1, 3, 3, 3$.

## Proof

Aiming for a contradiction, suppose there exists a simple graph $G = \struct {V, E}$ with $4$ vertices $v_1, v_2, v_3, v_4$ whose degrees are $1, 3, 3, 3$.

Without loss of generality, let $\map \deg {v_1} = 1$.

Then each of $v_2$, $v_3$ and $v_4$ are of degree $3$.

So each of $v_2$, $v_3$ and $v_4$ are joined to all the other vertices.

That includes $v_1$.

So that means $v_1$ is joined to each of $v_2$, $v_3$ and $v_4$

But that means $v_1$ is of degree $3$.

This contradicts the supposition that $\map \deg {v_1} = 1$.

$\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 $4$