Simple Graph whose Vertices Incident to All Edges

Theorem

Let $G = \struct {V, E}$ be a simple graph whose vertices are incident to all its edges.

Then $G$ is either:

the star graph $S_2$, which is also the complete graph $K_2$

an edgeless graph of any order.

Proof

If $G$ has no edges, then all the vertices are incident to all the edges vacuously.

So any of the edgeless graphs $N_n$ for order $n \in \Z_{\ge 0}$ fulfils the criterion.

Suppose $G$ has more than $2$ vertices $v_1, v_2, v_3$ and at least one edge.

Without loss of generality, let one edge be $v_1 v_2$.

But $v_3$ cannot be incident to edge $v_1 v_2$.

So $G$ can have no more than $2$ vertices.

Furthermore, there can be only one edge joining those two vertices.

The result follows from inspection of $K_2$ and $S_2$.

$\blacksquare$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.3$: Graphs: Problem $22$