Graph Theory homework Help at TutorEye

## Top Questions

t schedule 3 people for the day my % scheduled is 78.57% My question is how did the computer come up with the 78.57%?
View More

I would love to get a written solution. I did the other proof tree that you can see in the attaached files. So its supposed to look like that Thank You.
View More

xtbook. i really need in in half an hour
View More

## 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

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

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

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

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

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

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

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

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

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