Threadsafe factory pattern

I'am coding some simple graph manager and i decied to use factory pattern to create edges for my graph. I'am just beginning to learn design-patterns and threads.

I created factory with return some objects(edges), create method, code:

public Edge<T> CreateEdge(Vertex<T> firstVertex, Vertex<T> secondVertex)
{
    var edge = new Edge<T>(firstVertex, secondVertex, NextIndex);

    IncreaseIndex();

    return edge;
}

And here is my problem. What if that factory will be shared by multiple threads is possible that the return several edges with same index.

What is the best solution of this problem?
Should i use lock or some mutex?
Or it is the fault of my bad design classes, use factory?