Proof: Let C be a shortest cycle in G. If g(G)>= 2diam(G) + 2, then C has two vertices whose distance in C is at least diam(G)+1.(adsbygoogle = window.adsbygoogle || []).push({});

Question: why is it at least diam(G)+1?

cont. of proof: In G, these vertices have a lesser distance; any shortest path P between them is therefore not a subgraph of C.

how i understood: A path "around" the cycle creates a longer path than the shortest path between x and y in G. Therefore, this shortest path P is not a subgraph of the shortest cycle C.

rest of the proof: Thus, P contains a C-path xPy. Together with the shorter of the two x-y paths in C, this path xPy forms a shorter cycle than C, a contradiction.

Question: why does P contain a C-path xPy if it is not a subgraph of C?

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# A Every graph GG containing a cycle satisfies g(G)≤2d+1

Tags:

Have something to add?

Draft saved
Draft deleted

Loading...

Similar Threads - Every graph containing | Date |
---|---|

B Basic Graphing | Mar 9, 2018 |

I For every finite integer sequence there's a pattern- source? | Dec 26, 2017 |

I Why is the empty set a proper subset of every set? | Sep 16, 2016 |

Does every curve have a function? | Feb 23, 2015 |

Every Action That Has a Risk Indirectly Affects Your Lifespan? | Aug 18, 2014 |

**Physics Forums - The Fusion of Science and Community**