Graph Theory Quiz- Dual Graph

The dual of a plane graph is obtained by:

• Removing vertices

• Reversing edges

• Placing vertices in each face and joining them across original edges

• Deleting regions

The dual of the dual of a connected plane graph is:

• Always the original graph

• Always a tree

• Always disconnected

• A complete graph

In a dual graph, each edge corresponds to:

• A vertex in the original graph

• An edge in the original graph

• A path in the original graph

• A cycle in the original graph

Which of the following is true about dual graphs?

• Every planar graph has a unique dual

• Dual graphs may not be unique (depends on embedding)

• Dual graphs are always trees

• Dual graphs are never planar

A pendant edge in a graph corresponds to what in its dual?

• A cut edge

• A pendant vertex

• A cycle

• A face of degree one

The dual of a tree is:

• A complete graph

• A cycle

• A single vertex with loops

• A disconnected graph

If the original graph is connected, then its dual graph is:

• Always disconnected

• Always connected

• Complete

• Tree

The number of vertices in the dual graph equals:

• The number of vertices in the original

• The number of edges in the original

• The number of faces in the original

• None of these

The Cartesian product of sets A×B is defined as:

• All unions of elements of A and B

• All ordered pairs (a, b) with a∈A,b∈B

• All subsets of A and B

• None of these

The number of elements in A×B, where |A|=m and |B|=n, is:

• m + n

• m × n

• 2^(m+n)

• m - n