I know that we can check existence of cycle in graph by simply traversing the graph and check whether the vertex has been visited.
However, if there are only number of vertices and their corresponding degree known, can we check if the graph contains at least a cycle? Provided that there is no self-loop and no cycle involving exactly only 2 vertices with 2 degrees each. So it doesn't matter how they are connected to each other.
Is that possible without first randomly connecting each vertex according to the their degrees and then traversing the graph?
Actually the problem is to find a maximum value from a set of vertices if the vertex connected to other vertex. So let say I'm provided with a set of number $M$ and $|M| = |V| - 1$ with $V$ being a set of vertices, $M_n$ being the value that a vertex can have if the vertex is connected to $n$ other vertices (degree).
$$M = (4, 1, 1, 3, 2)$$ In that case the $|V|=6$ and let say $V=(V_1,....,V_6)$. That means if any of those vertices is connected to a vertex the value of both vertices would be $4$ ($M_1=4$, degree = 1) but if connected to other 3 vertices the value of that particular vertex would be $1$ ($M_3=1$, degree = 3).
From that, I'd like to find which combination yields the most value without introducing a cycle in the graph.
At first I was thinking of trying each combination one-by-one and constructing a graph from each combination then look for a cycle. However that approach wouldn't be feasible if there are a lot of vertices. So now I'm thinking of sorting the degree ($n$) first by the value ($M_n$) then start from there and thinking if it'd be possible to detect a cycle without constructing a graph.