Graphs

Lecture-1

Without talking much about the basics, I will be directly moving to the major and important theorems.

Theorem 1: For an undirected graph $G=(V,E)$ , then we have $\sum\limits_{v\in V}deg(v)=2m$ where $m$ is the number of edges. 

This is also called the 'Handshaking Lemma'. Based on this, we can say that the number of vertices of odd degrees is even. 

For a directed graph, it is interesting to note that 

$\sum\limits_{v\in V} indeg(v)=\sum\limits_{v\in V} outdeg(v) = m$. 

(Here $indeg$ and $outdeg$ refers to the in-degree and out-degree of the vertices.)

Theorem 2: A graph $G=(V_1,V_2,E)$ is bipartite if and only if every cycle is of even length.