PG Graph Theory-Quiz II

If G is a connected plane graph of order n, size m and having r regions, then _________ .

• n - m = 2

• n - m + 2r = 2

• n - m + r = 2

The chromatic number of every planar graph is ________

• atmost 4

• atleast 4

• equal to 4

The subdivision of a planar graph is non-planar

• False

• True

A tournament is an orientation of a _______ graph

• bipartite

• complete bipartite

• complete

• disconnected

A nontrivial connected graph G has a strong orientation if and only if G is ________

• vertex connected

• 2-edge connected

• edge connected

Every vertex in a nontrivial strong tournament belongs to a ________

• circle

• square

• triangle

A nontrivial connected graph D is Eulerian if and only if od v = id v for every vertex v of D

• True

• False

A nontrivial connected graph G has a strong orientation if and only if G contains no _________

•  bridge

• closed spanning walk

• path

• cycle

If a digraph D contains a u-v walk of length l then D contains a u-v path of length atleast l

• False

• True