Finals Quiz #2 - Graph Theory (B)

The historical 'Seven Bridges of Königsberg problem sought to determine if a person could walk through the city and achieve which specific goal?

• Visit each of the four landmasses exactly once

• Cross only bridges that connected the islands to the north bank

• Build a new bridge to create a perfect cycle

• Cross each of the seven bridges exactly once

According to the Handshake Lemma, if a graph has exactly 12 edges, what must be the sum of the degrees of all its vertices?

• 24

• 12

• 144

• 6

What is the requirement for two graphs, G1​ and G2​, to be considered 'isomorphic'?

• They must have the exact same names for all vertices in their sets

• There must be a bijection between their vertex sets that preserves adjacency

• They must both be connected and contain the same number of cycles

• One must be an induced subgraph of the other

A specific type of graph that is connected and contains no cycles is known as a:

• Complete Graph

• Directed Graph

• Tree

• Multigraph

A specific type of graph that is connected and contains no cycles is known as a:

• Complete Graph

• Directed Graph

• Tree

• Multigraph

What distinguishes an 'induced subgraph' G′=(V′,E′) from a general subgraph?

• It must not contain any cycles present in the original graph

• It must contain all the original vertices from the parent graph

• It must be a connected graph, even if the parent graph was disconnected

• It must include every edge from the original graph whose endpoints are both in the new vertex set

Which of the following must be true about the number of vertices with an odd degree in any given graph?

• There can only be at most two such vertices

• The number of such vertices must be even

• Every vertex in a connected graph must have an even degree

• He number of such vertices must be odd

If a graph has vertex degrees of 3, 2, 2, and 1, how many edges does it contain?

• 4

• 6

• 8

• 3

True or False: In any graph, the number of vertices with an odd degree must be even.

• True
• False

Which of the following describes a 'Cycle' in graph theory?

• A sequence of vertices where every vertex is visited exactly once

• A path that starts and ends at the same vertex without repeating edges

• An edge that connects a vertex to itself

• A graph that has no edges crossing each other