Definition:Odd Vertex (Graph Theory)

From ProofWiki
Jump to navigation Jump to search

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

K4.png


Graph with 2 Odd Vertices

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

Chartrand-exercise-2-1-7ef.png


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

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

Chartrand-exercise-2-1-8.png

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


Also see


Sources