Question

For each of these properties, determine whether it is monotone increasing and determine whether 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 four.

g) The graph G has radius three.

h) The graph G has diameter three.

Short answer

(a)This is monotone increasing.

(b) It is a monotone decreasing.

(c)This is not monotone increasing or monotone decreasing.

(d)It is monotone increasing.

(e)It is monotone decreasing.

(f)This is neither monotone increasing nor monotone decreasing.

(g)This is neither monotone increasing nor monotone decreasing.

(h)This is neither monotone increasing nor monotone decreasing

Step-by-step solution

(a) The graph G is connected

This property is monotone increasing since adding edges can only help in making the graph connected. It is not monotone decreasing, because by removing edges one can disconnect a connected graph.

(b) The graph G is not connected

It is a monotone decreasing. Since removing edges from a non-connected graph cannot possibly make it connected, while adding edges can make it possible.

(c) The graph G has an Euler circuit

Here, we cannot have either monotone increasing or monotone decreasing.

For example, the graph \({C_4}\), a square having an Euler circuit. In case, we have add one edge or remove one edge, then the resulting graph will not have an Euler circuit.

(d) The graph G has a Hamilton circuit

Here, the property is monotone increasing (because the extra edges do not interfere with the Hamilton circuit already there) but not monotone decreasing (e.g., start with a cycle).

(e) The graph G is planar

It is a monotone decreasing because if a graph can be drawn in plane, then each of its sub graphs can also be drawn in the plane.

However the property is not monotone increasing, let us take an example, add the missing edge to the complete graph on five vertices minus an edge to the complete graph on five vertices minus an edge changes the graph from being planar to being non planar.

(f) The graph G has chromatic number four

Here we have is neither monotone increasing nor monotone decreasing.

Let us take an example \({C_5}\), adding edges increases the chromatic number and removing them decreases it.

(g) The graph G has radius three

Here we have is neither monotone increasing nor monotone decreasing since adding edges can easily decrease the radius and removing them can easily increase it.

Take an example\({C_7}\)has radius three, but adding enough edges to make\({K_7}\)reduces the radius to 1, and removing enough edges to disconnect the graph makes the radius infinite.

(h) The graph G has diameter three

Here we have is neither monotone increasing nor monotone decreasing since adding edges can easily decrease the radius and removing them can easily increase it (diameter being twice the radius).