A property retained whenever additional edges are added to a simple graph (without adding vertices) is called a monotone-increasing property; a property that is retained whenever edges are removed (without removing vertices) is called a monotone-decreasing property. For each of the following, determine whether it is monotone increasing and determine if it is monotone decreasing:
a. The graph G is connected;
b. The graph G is not connected;
c. The graph G has an Euler circuit;
d. The graph G has a Hamilton circuit;
e. The graph G is planar;
f. The graph G has chromatic number Ο‡ = 4;
g. The graph G has radius r = 3;
h. The graph G has diameter d = 3.



Answer :

Other Questions