Graph Theory
Graph theory was discovered by Swiss mathematician Leonhard Euler in the 18th century. It involves the study of graphs to find the shortest path. A graph is a diagrammatical mathematical relation between objects, it has vertices which are known as nodes and these nodes are connected by edges which are known as links or lines hence a graph consists of lines and points. Graph is represented by G= (v , e) where v is the set of vertices and e is the set of edges. Graph theory has many advantages such as it is used in the study of algorithms, representing networks and data organization in computer science. In Google Maps graph theory is used to find the shortest path in roads between two points.
In science graph theory can be used to study and construct the three dimensional structure of molecules.
Graph Theory Sample Questions:
Question 1: What are the total number of edges in any tree with 20 vertices
(a) 18
(b) 19
(c) 20
(d) 21
Answer: (b)
Explanation: A tree has n-1 number of edges if it has n vertices.
Question 2: An isolated vertex has a degree of
(a) One
(b) Two
(c) Zero
(d) None of these
Answer: (c)
Explanation: Degree of vertex is the number of edges incident to the vertex, in isolated vertex there is no edge hence the degree is 0.
Question 3: The size of adjacency matrix of K5
(a) 5 x 5
(b) 3 x 4
(c) 5 x 10
(d) None of these
Answer: (a)
Explanation: The size of adjacency matrix is given by (vertex) x (vertex) i.e. 5 x 5
Question 4: K6 is non planar graph because
(a) It is subgraph of K7
(b) It is simple graph
(c) It has 5 vertices
(d) None
Answer: (a)
Explanation: K7 is a non planar graph and K6 its subgraph and it is a non planar.
Question 5: What is the circuit rank of K4
(a) 1
(b) 2
(c) 3
(d) 4
Answer: (c)
Explanation: Circuit Rank = m-n+1 where m is number of edges and n is the number of vertices
Question 6: In regular graph
(a) Degree of all vertices are equal
(b) Degree of all edges are equal
(c) Degree of all are zero
(d) None of these
Answer: (a)
Explanation: In regular graph degree of all vertices are equal
Question 7: Which graph follows the Hamiltonian cycle
(a) Petersen graph
(b) Any complete graph
(c) Butterfly graph
(d) All of them
Answer: (b)
Explanation: Any complete graph follows the Hamiltonian cycle
Question 8: How many maximum edges includes in simple graph with 6 vertices
(a) 11
(b) 10
(c) 5
(d) 15
Answer: (d)
Explanation: The maximum number of edges with n vertices are 
Question 9: Find the number of edges in complete bipartite graph K3,5
(a) 16
(b) 15
(c) 8
(d) None of These
Answer: (b)
Explanation: In a complete bipartite graph Km,n [m x n = Edges and m+n = Vertices ]
Question 10: In which type of walk there is no repetition of edge
(a) Path
(b) Circuit
(c) Trail
(d) Walk
Answer: (c)
Explanation: An open walk with no repetition of edge is known as Trail..
Take Graph Theory Homework Help Today!