2
$\begingroup$

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?

Edit

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).

Eg.

$$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.

$\endgroup$
4
  • 1
    $\begingroup$ Related post: Algorithm to check whether a graph has no cycles. $\endgroup$
    – amWhy
    May 18 '13 at 23:54
  • $\begingroup$ Are you saying that all we are given is the number $n$ of vertices, and the degrees $(d_1,d_2,\ldots,d_n)$ of each vertex, and we are to determine if the graph has a cycle? $\endgroup$
    – Samuel
    May 18 '13 at 23:56
  • $\begingroup$ @amWhy yeah that's what I am thinking, using DFS. However I'm wondering in my case, would it be possible without constructing the graph first? $\endgroup$
    – user78431
    May 19 '13 at 3:01
  • $\begingroup$ @Samuel, yup, is that possible? $\endgroup$
    – user78431
    May 19 '13 at 3:02
1
$\begingroup$

If you have an $n$-vertex graph with $n$ or more edges, there must be a cycle. You can calculate the number of edges from the degree sequence using the Handshaking Lemma.

If the $n$-vertex graph has $n-1$ or fewer edges, provided there are two vertices of degree $2$ or more, it may contain a cycle (or it may not). For example, these two graphs have the same degree sequences but only the first one has a cycle:

Cycle/no cycles

If you also knew the number of components $c(G)$ of the graph $G=(V,E)$ you could determine whether or not there is a cycle. Specifically, a graph is acyclic if and only if $c(G)=|V|-|E|$.

$\endgroup$
1
  • $\begingroup$ The only thing I need to check is the cycle itself, if a set contains a cycle, I don't need to check the rest of possible graph constructed of that set of degrees $\endgroup$
    – user78431
    May 19 '13 at 11:49
0
$\begingroup$

if there are only number of vertices and their corresponding degree known, can we check if the graph contains at least a cycle?

Do you mean a complete cycle (Hamiltonian) or any cycle at all? Vertex degrees fail in some strong ways for the problem of a complete cycle, because degree-based tests are too fast to be able to solve NP-complete problems. To test if there is any cycle is to test whether the graph is a union of trees, which is computationally simple, number of edges = $n$ - (number of connected components), but that is not a local condition that can be determined by degrees of vertices.

A set of vertex degrees forces Hamiltonicity if and only if it satisfies Chvatal's numerical condition (as in the Bondy-Chvatal theorem, http://books.google.com/books?id=zxSmHAoMiRUC&pg=PA198 ), and non-Hamiltonicity is forced only in trivial situations like not having enough edges to form a complete cycle. Most sets of vertex degrees are consistent both with a Hamilton cycle existing, and with a cycle not existing, so that there is not enough information in the degrees to test for a Hamiltonian cycle. Degree-based tests and other local methods that look only a finite distance away from each vertex have polynomial run-time, but testing Hamiltonicity is NP-complete, which makes local tests hopeless for general graphs.

$\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.