I'm writing a piece of code, and in the program that I'm writing, the user of the program will enter the number of vertices and the number of edges in a graph. With the number of vertices and the number of edges, I will need to show the user the vertex with the highest degree, but the graph isn't even written. How am I supposed to find the degree of vertex just given the number of vertices and the number of edges?
$\begingroup$
$\endgroup$
You can't, except for some special cases. A small example showing that you can't is given by considering a claw graph and a $P_4$ (path graph on four vertices. Both these graphs have four vertices and three edges, but the former has maximum degree 3 and the latter maximum degree 2.
$\begingroup$
$\endgroup$
You can't. As a simple example, consider four vertices and four edges. You could have a square or you could have a triangle with a tail off one vertex. The first has two vertices of degree two and the second has a vertex of degree three. With more vertices you can get more possibilities.
answered Nov 29 '17 at 3:23
