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