Simple Graph where All Vertices and All Edges are Adjacent
Theorem
Let $G$ be a simple graph in which:
and:
Then $G$ is of order no greater than $3$.
Proof
It is seen that examples exist of simple graphs which fulfil the criteria where the order of $G$ is no greater than $3$:
The cases where the order of $G$ is $1$ or $2$ are trivial.
When the order of $G$ is $3$, the criteria can be verified by inspection.
Let the order of $G = \struct {V, E}$ be $4$ or more.
Let $v_1, v_2, v_3, v_4 \in V$.
Suppose every vertex is adjacent to every other vertex.
As $v_1$ is adjacent to $v_2$, there exists the edge $v_1 v_2$.
As $v_3$ is adjacent to $v_4$, there exists the edge $v_3 v_4$.
But $v_1 v_2$ and $v_3 v_4$ both join two distinct pairs of vertices.
Thus $v_1 v_2$ and $v_3 v_4$ are not adjacent, by definition.
So when there are $4$ or more vertices in $G$, it cannot fulfil the criteria.
$\blacksquare$
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.3$: Graphs: Problem $19$