• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q53SE

Expert-verified
Found in: Page 738

### Discrete Mathematics and its Applications

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.

See the step by step solution

## Step 1: (a) Find the diameter

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.

## Step 2: (b) Find the diameter

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.

## Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.