## Graph Theory Module 1

### Theorem 1.1 - HandShaking Theorem

It states that the sum of degree of vertices of a graph is twice the no. of edges of $$G\ = (V,E)$$ be a graph with $$E$$ edges then

$$\sum deg_{G}(V)=2E$$

### Theorem 1.2

The no of vertices of odd degree in a graph is always even

### Theorem 1.3

The maximum degree of simple graph with $$n$$ vertices is $$n-1$$

### Theorem 1.4

The maximum number of edges in a simple graph of $$n$$ vertices are $$\frac{n(n-1)}{2}$$

### Theorem 1.5

If a graph*(connected or disconnected)* has exactly 2 vertices of odd degree, there must be a path joining the 2 vertices

### Theorem 1.6

A graph is disconnected if and only if it's vertex set $$V$$ can be partitioned into two nonempty disjoint subsets $$V_1 and\ V_2$$ such that there exists no edge in $$G$$ whose one end end vertex is in subset $$V_1$$ and the other in subset $$V_2$$.

### Theorem 1.7

A simple graph with $$n$$ vertices must be connected if it has more than $$\frac{\big[(n-1)(n-2)\big]}{2}$$ edges

### Theorem 1.8

A simple graph(without $$\parallel$$ edges or self loops) with $$n$$ vertices and $$k$$ components can have at most $$\frac{(n-k)(n-k+1)}{2}$$ edges