Simple Graph whose Vertices all Incident but Edges not Adjacent
Jump to navigation
Jump to search
Theorem
Let $G = \struct {V, E}$ be a simple graph such that:
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
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.3$: Graphs: Problem $20$