YouTube Tending to Infinity
Theorems on Graph Theory: Proofs are required of all the theorems
*Theorem 1: (First Theorem of Graph Theory): The sum of the degrees of all vertices in a graph is twice the
number of edges in the graph.
Theorem 2. Prove that the maximum degree of any vertex in a simple graph with n vertices is n - 1.
𝑛(𝑛 −1)
*Theorem 3: The maximum number of edges in a connected simple graph with n vertices is 2
*Theorem 4: The number of odd vertices in any graph is even. 2018,
Note: The number of even vertices may be odd or even.
𝑛(𝑛 − 1)
Theorem 5: Prove that a complete graph with n vertices consists of number of edges.
2
*Theorem 6: The minimum number of edges in a connected graph with n vertices is n-1. 2023
Theorem 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.
* Theorem 8: A simple graph with n number of vertices and k number of components can have maximum
(𝑛 − 𝑘)(𝑛−𝑘+1)
number of edges. 2023, 2018, 2007,2008,2009,2010,2013,2015
2
Theorem 9: If 𝛿(𝐺) and ∆(𝐺) be the min degree and max degree of an (p, q) graph respectively. Prove that
2𝑞
𝛿(𝐺) ≤ 𝑝 ≤ ∆(𝐺) 2023,
𝑛+1
Theorem 10: Prove that the number of pendant vertices in a binary tree is where n is the number of
2
vertices in the tree.
*Theorem 11: Prove that a tree with n vertices contains exactly (n-1) edges.
Theorem 12: Prove that a graph G has a spanning tree if and only if G is connected.
*Theorem 13. (Euler’s formula) : A connected planar graph G with n vertices and e number of edges
determines f = e-n+2 number of regions.
Theorem 14: A planar graph G with n vertices, e number of edges and k number of connected components
determines f = e-n+k+1:
Theorem 15: Let G be a simple connected planar graph with. n vertices, e edges and f regions (faces). Then
3
(1)𝑒 ≥ 𝑓 (2)𝑒 ≤ 3𝑛 − 6.
2
Theorem 16: The chromatic number of a complete graph with n vertices (Kn) is n.
Theorem 17: The chromatic number of a cycle with n vertices is (i) 2, if n is even (ii) 3, if n is odd.
Theorem 18: The chromatic number of a non-null graph is 2 if and only if the graph is bi-partite.
Theorem 19: A Tree with two or more vertices has chromatic number 2.
ALL THE BEST!!
