Simple Graph where All Vertices and All Edges are Adjacent

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $G$ be a simple graph in which:

every vertex is adjacent to every other vertex

and:

every edge is adjacent to every other edge.

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$:

All-Vertices-and-Edges-Adjacent.png

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