#PEP-8 class vertex: class graph:

PEP-8 asks that you name these Vertex and Graph, with initial capital.

#naming nodes

 self.key = key

Yes, you will be using this as a dict key. But name would have been the more natural identifier for a node name.

#unused attribute

Please delete this line:

 self.nbnodes = 0

That quantity may be trivially obtained with len(self.root), and in any event you never reference it.

#edge weight At first blush this appears to be a default edge ID of zero:

def add(self, key1, key2, edge=0):

Later it looks more like an edge weight, an attribute of the edge. It would be helpful for a docstring to clarify this. Or just name it edge_weight.

#API Consider having cutver() print nothing, and instead return a result which the caller may print.

Also, _cutver() feels a lot like a Fortran subroutine, as it has side effects on the result parameter, rather than returning a result.

#sentinel You use this:

 parent[vertex] = -1

without every verifying that a node name is not -1, or constraining each node name to be a str. The usual convention would be to use None to represent this.

docstring

 self.curr = 0

This is absolutely not self-descriptive enough. Use a """docstring""" or # comment to tell us what quantity it is measuring.

reference

In general _cutver() is obscure, which increases the difficulty of answering your two questions. It cites no references and does not attempt to justify any of its algorithmic steps. Perhaps it correctly finds cut vertices, but the text does not give us any reason to see why that is obviously true. If the code tries to adhere to Hopcroft73 (with Tarjan, algorithm 447), then choosing to omit identifiers like lowpoint is not helping the reader to see how the current implementation corresponds to what Hopcroft describes.

PEP-8

class vertex:
class graph:

PEP-8 asks that you name these Vertex and Graph, with initial capital.

naming nodes

 self.key = key

Yes, you will be using this as a dict key. But name would have been the more natural identifier for a node name.

unused attribute

Please delete this line:

 self.nbnodes = 0

That quantity may be trivially obtained with len(self.root), and in any event you never reference it.

edge weight

At first blush this appears to be a default edge ID of zero:

def add(self, key1, key2, edge=0):

Later it looks more like an edge weight, an attribute of the edge. It would be helpful for a docstring to clarify this. Or just name it edge_weight.

API

Consider having cutver() print nothing, and instead return a result which the caller may print.

Also, _cutver() feels a lot like a Fortran subroutine, as it has side effects on the result parameter, rather than returning a result.

sentinel

You use this:

 parent[vertex] = -1

without every verifying that a node name is not -1, or constraining each node name to be a str. The usual convention would be to use None to represent this.

docstring

 self.curr = 0

This is absolutely not self-descriptive enough. Use a """docstring""" or # comment to tell us what quantity it is measuring.

reference

In general _cutver() is obscure, which increases the difficulty of answering your two questions. It cites no references and does not attempt to justify any of its algorithmic steps. Perhaps it correctly finds cut vertices, but the text does not give us any reason to see why that is obviously true. If the code tries to adhere to Hopcroft73 (with Tarjan, algorithm 447), then choosing to omit identifiers like lowpoint is not helping the reader to see how the current implementation corresponds to what Hopcroft describes.