Simple Graph whose Vertices all Incident but Edges not Adjacent

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $G = \struct {V, E}$ be a simple graph such that:

every vertex is incident with at least one edge
no two edges are adjacent to each other.


Then $G$ has an even number of vertices.


Proof

Suppose there exists a set of $3$ vertices that are connected.

Then at least one of these vertices has at least $2$ edges.

That would mean that at least $2$ edges were incident with the same vertex.

That is, that at least $2$ edges were adjacent to each other.

So, for a simple graph to fulfil the conditions, vertices can exist only in $2$-vertex components.

So such a simple graph must have an even number of vertices.

$\blacksquare$


Sources