Which of the following statements for a simple graph is correct?
a) Every path is a trail
b) Every trail is a path
c) Every trail is a path as well as every path is a trail
d) Path and trail have no relation
Option : a
Explanation: In a walk if the vertices are distinct it is called a path, whereas if the
edges are distinct it is called a trail.
In the given graph identify the cut vertices.
a) B and E
b) C and D
c) A and E
d) C and B
Option : d
For the given graph(G), which of the following statements is true?
a) G is a complete graph
b) G is not a connected graph
c) The vertex connectivity of the graph is 2
d) The edge connectivity of the graph is 1
Option : c
What is the number of edges present in a complete graph having n vertices?
a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient
Option : b
The given Graph is regular.
a) True
b) False
Option : a
Explanation: In a regular graph, degrees of all the vertices are equal. In the given
graph the degree of every vertex is 3
In a simple graph, the number of edges is equal to twice the sum of the degrees of
the vertices.
a) True
b) False
Option : b
Explanation: The sum of the degrees of the vertices is equal to twice the number of
edges.
A connected planar graph having 6 vertices, 7edges contains
regions.
a) 15
b) 3
c) 1
d) 11
Option : b
Explanation: By euler’s formula the relation between vertices(n), edges(q) and
regions(r) is given by n-q+r=2.
What is the maximum number of edges in a bipartite graph having 10 vertices?
a) 24
b) 21
c) 25
d) 16
Option : c
Explanation: Let one set have n vertices another set would contain 10-n vertices.
Total number of edges would be n*(10-n), differentiating with respect to n, would
yield the answer.
Which of the following is true?
a) A graph may contain no edges and many vertices
b) A graph may contain many edges and novertices
c) A graph may contain no edges and no vertices
d) A graph may contain no vertices and many edges
Option : b
Explanation: A graph must contain at least one vertex.
For a given graph G having v vertices and e edges which is connected and has no
cycles, which of the following statements is true?
a) v=e
b) v = e+1
c) v + 1 = e
d) v = e-1
Option : b
Explanation: For any connected graph with no cycles the equation holds true
A graph with all vertices having equal degree is known as a
a) Multi Graph
b) Regular Graph
c) Simple Graph
d) Complete Graph
Option : b
Explanation: The given statement is the definition of regular graphs.