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
    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
    OK thanks; got it!2012-12-14