StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q53SE

Expert-verifiedFound in: Page 738

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**a) Show that if the diameter of the simple graph **\({\bf{G}}\)** is at least four, then the diameter of its complement **\({\bf{\bar G}}\)** is no more than two.**

** **

**b) Show that if the diameter of the simple graph**\({\bf{G}}\)** is at least three, then the diameter of its complement **\({\bf{\bar G}}\)** is no more than three.**

(a) This gives a path of length less than or equal to 3 from \(x\)to\(y\) in \(G\)which is a contradiction.

(b) Here, \(u,y,x,v\)is a path of length 3 in\(G\), as required.

Let us take a graph\(G = \left( {V,E} \right)\), having \(u,v\)as vertices. It must show that the distance between \(u\) and \(v\) in \(\bar G\) is at most 2 as per the questions demands.

It has the condition that \(\left\{ {u,v} \right\} \notin E\)this distance is 1, so it will have to mandatorily consider \(\left\{ {u,v} \right\} \in E\){since the diameter of\(G \ge 3\)}, there are vertices \(x\)and \(y\)such that the distance in \(G\)between \(x\)and \(y\)is greater than 3.

So, in the set of \(\left\{ {u,v} \right\}\)neither \(x\)nor\(y\), nor even both are present. Suppose that \(x\)is different from both \(u\) and\(v\), either \(\left\{ {u,x} \right\}\)or\(\left\{ {v,x} \right\} \notin E\), otherwise \(u,x,v\)would be a path in \(G\)of length 2.

Hence, it can assume\(\left\{ {u,x} \right\} \notin E\).

Thus \(x\)cannot be \(u\) or\(v\), and similar by approach either \(\left\{ {u,y} \right\} \in E\)or\(\left\{ {v,y} \right\} \in E\).

In either case, this gives a path of length less than or equal to 3 from \(x\)to\(y\) in \(G\)which is a contradiction.

Let us take a graph\(G = \left( {V,E} \right)\) and\(\left\{ {u,v} \right\} \in V\).

It must show that the distance between \(u\)and \(v\)in\(G < 3\). To prove \(\left\{ {u,v} \right\} \notin V\) it goesto the other way round and assume \(\left\{ {u,v} \right\} \in E\)(since the diameter of G is greater than 3), so there must be vertices \(x\)and\(y\)such that the distance in \(G\)between \(x\)and\(y\)is\( > 3\).

Either\(x\),\(y\)or both, \( \notin \left\{ {u,v} \right\}\).Now it has to assume that \(x\)is different from both of the \(u\)and\(v\), either \(\left\{ {u,x} \right\}\)or \(\left\{ {v,x} \right\}\) belongs \(E\), otherwise \(u,x,v\)would be a path in \(G\)of length 2.

Hence, it can assume\(\left\{ {u,x} \right\} \in V\).Thus \(x\) cannot be \(u\)or \(v\).If \(\left\{ {u,y} \right\} \in E\)then \(x,u,y\)is a path of length 2 in\(G\), so \(\left\{ {u,y} \right\} \notin E\) and thus\(\left\{ {v,y} \right\} \in E\).

Hence,\(\left\{ {u,y} \right\} \notin E\), otherwise \(x,v,y\)is a path of length 2 in\(G\).Thus \(u,y,x,v\)is a path of length 3 in\(G\), as required.

94% of StudySmarter users get better grades.

Sign up for free