Definition:Odd Vertex (Graph Theory)

Definition

Let $G = \struct {V, E}$ be an undirected graph.

Let $v \in V$ be a vertex of $G$.

If the degree of $v$ is odd, then $v$ is an odd vertex.

Examples

Graph with All Odd Vertices

An example of a simple graph whose vertices are all odd includes the complete graph of order $4$:

Graph with 2 Odd Vertices

An example of a simple graph with $2$ odd vertices:

Graphs of Order $p$ with $n$ Odd Vertices

Examples of simple graphs of order $p$ with $n$ odd vertices for $0 \le n < p$ for various $p$ and $n$ are as follows:

Note that by the Handshake Lemma $n$ is always even.

Also see

• Definition:Even Vertex (Graph Theory)

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex
• 1992: George F. Simmons: Calculus Gems ... (previous) ... (next): Chapter $\text {A}.21$: Euler ($\text {1707}$ – $\text {1783}$)
• 1992: David Wells: Curious and Interesting Puzzles ... (previous) ... (next): The Bridges of Königsberg