Generalizing from my experience with Enterprise Objects (which Core Data evolved from) I would say that both of your scenarios would be equally fast without indexing and the second slightly slower with indexing.
Using and SQL store, the cost of adding one object is largely fixed regardless of how many other objects are in the graph. Indexing does cause a scaling effect because the index is dependent on other existing objects. However, in the vast majority of cases, this is not significant.
The more complex the relationships within the graph the more saves are impacted by total graph size. Obviously, if you have graph with only ten objects, then no relationship can have more than ten objects in it. If you have one with 10,000, the relationships are potentially much larger and take longer to process.
In sum, Core Data with an SQL store appears to be largely unaffected by just the size of the graph.