Some graph theory

graph G is an ordered pair (V,E) where V is a finite nonempty set of vertices and E is a set of two-element subsets of V called edges. By convention, we write uv to denote an edge \{u,v\}\in E. The degree of a vertex u\in V is the cardinality of the set \{v \in V: uv\in E\}. A graph G is said to be bipartite if V=V_1\cup V_2 where V_1\cap V_2=\varnothing and uv\in E implies u\in V_1, v\in V_2 or v\in V_1, u\in V_2. Time for a little theorem:

If G is a graph that is not bipartite, then there exist u,v\in V such that \deg u + \deg v is even.

Proof: If there do not exist u,v\in V such that \deg u + \deg v is even, let

\begin{aligned}  V_1 &= \{v\in V : \deg v \text{ is even} \}\\  V_2 &= \{v\in V : \deg v \text{ is odd} \}  \end{aligned}

Then every edge in G contains a vertex from V_1 and a vertex from V_2. It follows that (V_1, V_2) is a bipartition of G, and hence that G is bipartite.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s