3
$\begingroup$

"We cannot create new cycles by deleting a vertex" - How is this true within this context?:

"Assume G is planar and has girth at least 6. If v is a vertex of degree at most 2, then G-v still has girth at least 6."

For instance, as a counterargument, take a hexagon as a graph. If we remove a vertex, then I get a graph WITHOUT girth at least 6.

  • 2
    If we delete a vertex from a hexagon we get a graph with no cycles, which by definition has infinite girth (clearly at least 6).2012-12-14
  • 0
    So since a tree is defined as a graph with no cycles, then it has infinite girth?2012-12-14
  • 2
    No cycles <=> infinite girth.2012-12-14

1 Answers 1

5

Deleting a vertex from a graph usually means deleting the vertex and all edges incident to it, not joining those edges in some way. So if you delete a vertex from a hexagon, you should get five vertices in a line: o-o-o-o-o

  • 0
    Oh OK, thanks for the clarification! But I still seem confused by the statements in my question :/2012-12-14
  • 3
    The girth of a graph is the length of the shortest cycle (if any). If there are no cycles, the girth is $\infty$. So deleting a vertex from the hexagon increases the girth from $6$ to $\infty$ (which is still "at least $6$")2012-12-14
  • 0
    OK thanks; got it!2012-12-14