0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.