Back
0

Connectivity

Description: Test your understanding of Connectivity in Graph Theory with these challenging questions.
Number of Questions: 15
Created by:
Tags: graph theory connectivity eulerian path hamiltonian path
Start the Quiz
Attempted 0/15 Correct 0 Score 0
‹
›

In a connected graph, if a vertex is removed, the resulting graph is:

  1. Always connected

  2. Always disconnected

  3. Sometimes connected and sometimes disconnected

  4. None of the above

Show answer
Correct Option: C
Explanation:

Removing a vertex from a connected graph can result in a connected or disconnected graph, depending on the specific graph structure.

A graph is said to be Eulerian if:

  1. It has an Eulerian path

  2. It has an Eulerian circuit

  3. It has both an Eulerian path and an Eulerian circuit

  4. None of the above

Show answer
Correct Option: B
Explanation:

An Eulerian graph is a graph that has an Eulerian circuit, which is a closed walk that visits every edge exactly once.

A graph is said to be Hamiltonian if:

  1. It has a Hamiltonian path

  2. It has a Hamiltonian circuit

  3. It has both a Hamiltonian path and a Hamiltonian circuit

  4. None of the above

Show answer
Correct Option: B
Explanation:

A Hamiltonian graph is a graph that has a Hamiltonian circuit, which is a closed walk that visits every vertex exactly once.

Which of the following statements is true about a connected graph?

  1. It has at least one cycle

  2. It has at least one path between any two vertices

  3. It has a unique Eulerian circuit

  4. All of the above

Show answer
Correct Option: B
Explanation:

A connected graph is a graph in which there is a path between any two vertices.

Which of the following statements is true about a tree?

  1. It is a connected graph

  2. It has no cycles

  3. It has a unique Eulerian path

  4. All of the above

Show answer
Correct Option: D
Explanation:

A tree is a connected graph with no cycles.

Which of the following statements is true about a bridge in a graph?

  1. It is an edge whose removal increases the number of connected components in the graph

  2. It is an edge whose removal decreases the number of connected components in the graph

  3. It is an edge whose removal does not change the number of connected components in the graph

  4. None of the above

Show answer
Correct Option: A
Explanation:

A bridge is an edge whose removal increases the number of connected components in the graph.

Which of the following statements is true about a cut vertex in a graph?

  1. It is a vertex whose removal increases the number of connected components in the graph

  2. It is a vertex whose removal decreases the number of connected components in the graph

  3. It is a vertex whose removal does not change the number of connected components in the graph

  4. None of the above

Show answer
Correct Option: A
Explanation:

A cut vertex is a vertex whose removal increases the number of connected components in the graph.

Which of the following statements is true about a block in a graph?

  1. It is a maximal connected subgraph

  2. It is a minimal connected subgraph

  3. It is a subgraph that contains all the cycles in the graph

  4. None of the above

Show answer
Correct Option: A
Explanation:

A block is a maximal connected subgraph of a graph.

Which of the following statements is true about a 2-connected graph?

  1. It has at least two paths between any two vertices

  2. It has at least two cycles

  3. It has a unique Eulerian circuit

  4. All of the above

Show answer
Correct Option: A
Explanation:

A 2-connected graph is a graph in which there are at least two paths between any two vertices.

Which of the following statements is true about a k-connected graph?

  1. It has at least k paths between any two vertices

  2. It has at least k cycles

  3. It has a unique Eulerian circuit

  4. All of the above

Show answer
Correct Option: A
Explanation:

A k-connected graph is a graph in which there are at least k paths between any two vertices.

Which of the following statements is true about a planar graph?

  1. It can be drawn on a plane without any edge crossings

  2. It has a unique Eulerian circuit

  3. It is always a tree

  4. None of the above

Show answer
Correct Option: A
Explanation:

A planar graph is a graph that can be drawn on a plane without any edge crossings.

Which of the following statements is true about a Kuratowski graph?

  1. It is a planar graph

  2. It is a non-planar graph

  3. It is a graph that contains a cycle of length 5

  4. None of the above

Show answer
Correct Option: B
Explanation:

A Kuratowski graph is a non-planar graph that contains a cycle of length 5.

Which of the following statements is true about a Petersen graph?

  1. It is a planar graph

  2. It is a non-planar graph

  3. It is a graph that contains a cycle of length 5

  4. All of the above

Show answer
Correct Option: B
Explanation:

A Petersen graph is a non-planar graph that contains a cycle of length 5.

Which of the following statements is true about a Tutte graph?

  1. It is a planar graph

  2. It is a non-planar graph

  3. It is a graph that contains a cycle of length 5

  4. None of the above

Show answer
Correct Option: B
Explanation:

A Tutte graph is a non-planar graph that contains a cycle of length 5.

Which of the following statements is true about a Heawood graph?

  1. It is a planar graph

  2. It is a non-planar graph

  3. It is a graph that contains a cycle of length 5

  4. None of the above

Show answer
Correct Option: B
Explanation:

A Heawood graph is a non-planar graph that contains a cycle of length 5.

- Hide questions
ADVERTISEMENT

Find more quizzes from top tags

general knowledge
3615 Quizzes
119858 Questions
 technology
307 Quizzes
36705 Questions
 sports
963 Quizzes
19148 Questions
 history
1187 Quizzes
13475 Questions
 physics
598 Quizzes
13441 Questions
 biology
1160 Quizzes
12174 Questions
 science & technology
551 Quizzes
11015 Questions
 chemistry
490 Quizzes
9892 Questions
 maths
518 Quizzes
9324 Questions
 softskills
0 Quizzes
7131 Questions