Prove that if diam(G)=3 for a regular graph G, then d i a m ( G ¯ ) = 2..I know that without using regularity one can show that if d i a m ( G ) ≥ 3 , then d i a m ( G ¯ ) ≤ 3. How do I use regularity to show that it must be exactly 2?

Question

Prove that if diam(G)=3 for a regular graph G, then   d  i  a  m  (            G      ¯        )  =  2..I know that without using regularity one can show that if   d  i  a  m  (  G  )  ≥  3  ,  then   d  i  a  m  (            G      ¯        )  ≤  3. How do I use regularity to show that it must be exactly 2?

Punktatsp · Accepted Answer

Suppose G is a graph with diam(G)&amp;gt;2 and       d    i    a    m    (          G      ¯        )  &amp;gt;  2  ;; I will show that G is not regular.More precisely, let   x  ,  y  ,  v  ,  w be vertices with       d    G    (  x  ,  y  )  &amp;gt;  2 and       d                  G        ¯              (  v  ,  w  )  &amp;gt;  2  ;; I will show that   deg  ⁡  (  v  )  +  deg  ⁡  (  w  )  &amp;gt;  deg  ⁡  (  x  )  +  deg  ⁡  (  y  )  ,, the degrees being computed in G.Clearly   x  ,  y  ,  v  ,  w are four distinct vertices,   v  w  ∈  E  (  G  )  , and   x  y  ∈  E  (      G    ¯    )  . Since       d                  G        ¯              (  v  ,  w  )  &amp;gt;  2  , at least one of the edges   x  v  ,  x  w is in E(G); without loss of generality, we assume that   x  v  ∈  E  (  G  )  . It readily follows that   y  v  ∈  E  (      G    ¯    )  ,     y  w  ∈  E  (  G  )  ,, and   x  w  ∈  E  (      G    ¯    )  ..Let   S  =  V  (  G  )  ∖  {  x  ,  y  ,  v  ,  w  }  .. Let m be the number of edges (of G) between S and   {  v  ,  w  }  ,, and let n be the number of edges between S and {x,y}. Then   deg  ⁡  (  v  )  +  deg  ⁡  (  w  )  =  m  +  4  ,, and   deg  ⁡  (  x  )  +  deg  ⁡  (  y  )  =  n  +  2.Since each vertex in S is joined (by an edge of G) to at least one vertex in   {  v  ,  w  } and to at most one vertex in {x,y}, we have   m  ≥  n  ;; it follows that   deg  ⁡  (  v  )  +  deg  ⁡  (  w  )  =  m  +  4  &amp;gt;  n  +  2  =  deg  ⁡  (  v  )  +  deg  ⁡  (  w  )  .

Prove that if diam(G)=3 for a regular graph G, then d i a m ( <mrow class="MJX-Te

Answered question

Answer & Explanation

New Questions in Descriptive Statistics