In a very narrow sense, the answer is "Yes": assuming that your base classes or interfaces are designed for a single purpose, inheriting both of them does create a class with multiple responsibilities. However, whether or not it is "a bad thing" depends on the nature of the classes or interfaces that you are inheriting.
You can partition your classes and interfaces into two major groups - the ones addressing the essential complexity of your system, and the ones addressing its accidental complexity. If you inherit from more than one "essential complexity" classes, it is bad; if you inherit from one "essential" and one or more "accidental" classes, it is OK.
For example, in a billing system you could have classes for representing invoices and billing cycles (they address the essential complexity) and classes for persisting objects (they address the accidental complexity). If you inherit like this
class BillingCycleInvoice : public BillingCycle, public Invoice {
};
it is bad: your BillingCycleInvoice has a mixed responsibility as it relates to the essential complexity of the system.
On the other hand, if you inherit like this
class PersistentInvoice : public Invoice, public PersistentObject {
};
your class is OK: technically, it services two concerns at once, but since only one of them is essential, you can write off inheriting the accidental one as the "cost of doing business".
I believe you've wandered into the field of over-engineering, chasing abstract principles instead of focusing on get things done in the simplest and most pleasant way.
Your (*) is a clear giveaway. OO can provide great help in managing complexity, but only as long as it's used as a tool to that goal. If instead you want to "write pure OO" instead of "solving my problem", it becomes a burden.
SRP is a similar thing -- it's well worth thinking. And especially good use to drive "extract" or "split" type of refactorings when your current code is overburdened with too many tasks. After addressing DRY usually we still have a plenty of options on packaging, and it is a matter of balance. Too big class is bad, but having it single has benefits. If the same task is done by 5 classes it may be way harder to follow. Especially if none of them have a chance to work alone, they are coupled with cross-calls in all directions. Such split might look good on dumb statistics but is bad for practice anyway.
So much for the theory, what about your case? You picked a border problem; indeed the function may not fit either Node or Edge. Though even that is hard to tell without the content, knowing what those actually do. Can I walk the graph having just a Node or an Edge? If I can, then adjacent may fit to that same group of functions.
Actually as soon as you have implementation of the function, it should be a great help to see where it fits better -- what data it had to fetch. Say, if it starts with getting the node and edge collections from Graph, why on earth is it not just member of Graph and play on the home ground?
A free function might also be fair game. A *Utils fake class that is really just a trash bin is probably the worst way, that hardly wins anything but adds to complexity. But a language or an ill-conceived policy may force that.
Best Answer
A good question and one I used to often mull over.
I would say not objective, no. Definitely subjective. How you approach breaking down problems depends on your philosophy toward that type of problem. Science shows us that there can be many different ways to solve the same problem effectively. Science also shows us that people continents apart can come up with the same solutions independently, and so some solutions are more obvious than others. In any case, judging solutions in terms of "best" depends on your criteria.
Really, what one might see as two parts of the same whole, another might see as two totally separate concepts. One sees this all the time when looking at how maintainers of different code libraries approach the same problem. And yet both solutions work just fine.
(PS. Edited this answer as the OP's final question asks the opposite of the question title.)