Some Important Theorem of Graph Theory

Some Important Theorem of Graph Theory

1. The maximum degree of any vertex in a graph with n vertices is n-1.

2. The maximum number of edges in a connected simple graph with n vertices is n(n-1)/2. 

3. The sum of the degrees of all vertices in a graph is twice the number of edges in the graph.

4. The number of odd vertices in any graph is even.

 (Note- The number of even vertices may be odd or even).

5. A complete graph with n vertices consists of n(n-1)/2 number of edges.

6. The minimum number of edges in a connected graph with n vertices is n-1.

7. The minimum number of edges in a simple graph (not necessarily connected) with n vertices is n-k, where k is the number of connected components of the graph.

8. In a di – graph, the sum of the out – degree of all vertices= the sum of the in – degrees of all vertices=number of edges in the graph.

9. A simple graph with n number of vertices & k components can have maximum (n-k)(n-k+1)/2 number of edges.

10. A simple graph with at least two vertices has at least two vertices of same degree.

11. Handshaking Theorem:- If G=(V,E) be an undirected graph with e edges, then sum of degrees of the vertices in an undirected  graph is even.

12. In a non – directed graph, the total number of odd degree is even.

13. If G=(V, E) be a directed graph with e edges, then the sum of the out degrees of the vertices of a diagraph G equals the sum of in degree of the vertices which equals the number of edges in G.