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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


Correct Option: B
Explanation:

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

- Hide questions