Hugo Kornelis offers a mea culpa:
In my post, I pointed out that SQL Server automatically creates a unique nonclustered index on the (internal and hidden) column graph_id, that you can delete, but can’t modify. I added that users cannot specify indexes on that column, nor on the other internal and hidden columns that exist in edge tables (from_obj_id, from_id, to_obj_id, and to_id). These statements are factually correct, but misleading.
I then concluded from those facts that once you delete the automatically generated index, you can not re-create it. This is actually incorrect.
Read on for the correct answer, as well as more information on indexing practices and advice on the right kinds of indexes to create on graph tables.