Is there a limit to how many edges a vertex can have?


#1

Question

In the context of this exercise, is there a limit to how many edges a vertex can have?

Answer

This can be dependent on your graph implementation, but generally, yes, there is a limit to the number of edges a vertex can have.

For an undirected graph, you can only have up to one edge between any pair of vertices. This would mean that if there are N total vertices in the graph, the maximum number of edges each vertex can have would be N - 1, with every vertex other than itself.

For a directed graph, you can have two directed edges between each pair of vertices (vertex_A and vertex_B), one going from vertex_A to vertex_B and one going from vertex_B to vertex_A. This would mean that a vertex can have at most 2N - 2 edges for a directed graph.