UNIT-4 MCQ

Which of the following statements for a simple graph is correct?

• a) Every path is a trail

• a) Every trail is a path

• a) Every trail is a path as well as every path is a trail

• a) Path and trail have no relation

1. What is the number of edges present in a complete graph having n vertices?

• (n*(n+1))/2

• (n*(n-1))/2

• N

• Information given is insufficient

A connected planar graph having 6 vertices, 7 edges contains _____________ regions.

• 15

• 3

• 1

• 11

Which of the following properties does a simple graph not hold?

• Must be connected

• Must be unweighted

• Must have no loops or multiple edges

• Must have no multiple edges

Which of the following is true?

• A graph may contain no edges and many vertices

• A graph may contain many edges and no vertices

• A graph may contain no edges and no vertices

• A graph may contain no vertices and many edges

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?

• v=e

• v = e+1

• v + 1 = e

• v = e-1

Which of the following ways can be used to represent a graph?

• Adjacency List and Adjacency Matrix

• Incidence Matrix

• Adjacency List, Adjacency Matrix as well as Incidence Matrix

• No way to represent

The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is ____________

• O(V)

• O(E²)

• O(E)

• O(V²)

Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is ________

• 2

• 4

• 6

• 8

For which of the following combinations of the degrees of vertices would the connected graph be eulerian?

• 1 2 3

• 2 3 4

• 2 4 5

• 1 3 5