Graph Theory homework Help at TutorEye
Flower

Are you a university or school looking for an online tutoring partnership ? Talk to Us

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.

 

Get the full solution!

 

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.

 

Get the full solution!

 

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 

 

Get the full solution!


 

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.

 

Get the full solution!


 

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

 

Get the full solution!


 

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

 

Get the full solution!


 

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

 

Get the full solution!


 

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 The maximum number of edges with n vertices are.

 

Get the full solution!


 

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 ]

 

Get the full solution!


 

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!

We Are Different from Others!

Help with Graph Theory