I am wondering. When  exactly  is the fresh new graph created?

It’s created during the forward pass. i.e. when you write something like:
loss = criterion(model(input), target)
The graph is accessible through loss.grad_fn and the chain of autograd Function objects.
The graph is used by loss.backward() to compute gradients.
optimizer.zero_grad() and optimizer.step() do not affect the graph of autograd objects. They only touch the model’s parameters and the parameter’s grad attributes.