Question

Show that the graph property \({\bf{P}}\) is monotone increasing if and only if the graph property \({\bf{Q}}\) is monotone decreasing, where \({\bf{Q}}\) is the property of not having property\({\bf{P}}\).

Short answer

Here, is a contradiction to our supposition.

Step-by-step solution

Introduction

A monotonic function is a function which is either entirely nonincreasing or non-decreasing. A function is monotonic if its first derivative (which need not be continuous) does not change sign.

Prove that P is monotone increasing

Let us take a simple graph\(G\). As per the questions we let that\(P\)is monotone increasing. We then consider a situation when the property of not having\(P\)were not sustained whenever the removal of edges is taking place from a simple graph, also there will be a simple graph\(G\)not having\(P\)and another simple graph\(G\)” with the same vertices but with some of the edges of\(G\)missing that has\(P\)

.

Since\(P\)is monotonically increasing, so because\(G\)has\(P\)as per our assumption, so does\(G\)obtained by adding edges to\(G\).

Here, is a contradiction to our supposition.

Prove that Q is monotone increasing

Let us take a simple graph\(G\). As per the questions we let that\(Q\)is monotone increasing. We then consider a situation when the property of not having\(Q\)were not sustained whenever the removal of edges is taking place from a simple graph, also there will be a simple graph\(G\)not having\(Q\)and another simple graph\(G\)” with the same vertices but with some of the edges of\(G\)missing that has\(Q\).

Hence, we prove our point.\(Q\)