Test by Bikram | Mathematics | Test 2 | Question: 3

Question

Read the following statements and identify the correct ones:

1. Any two simple connected graphs with $n$ vertices, where all vertices have degree two, are isomorphic.
2. The maximum vertex connectivity possible is $\lfloor 2e/n \rfloor$.
3. If $G$ is a simple graph that has a hamiltonian circuit, then $\text{deg}(u) + \text{deg}(v) \geq n$ for every pair of vertices for $n \geq 3$.
4. Number of edge disjoint hamiltonian circuit in a complete graph with n vertices is $\lfloor(n-1)/2\rfloor$ .

• A. I,II are correct.
• B. I,II,III are correct.
• C. I,II,IV are correct.
• D. I,IV are correct.

Answer 1

1. It should be correct as it is present in all the option.
2. For cycle graph (2e/n) = (2n/n) = 2. It is true because remove the opposite vertex, graph will become disconnected.
    For complete graph (2e/n) = (n(n-1)/n) = (n-1). It is true.
    So this option seem to be correct.

3. ORE's Theorem: If G is a simple graph with n vertices with n>= 3 such that deg(u) + deg(v) >= n for every pair of non-adjacent vertices u and v in G, then G has a hamiltonian cycle.

3 is wrong. Because It is sufficient condition not necessary. A graph having this deg(u) + deg(v) >= n as true will definitely have hamiltonian circuit. But it doesn't mean that a graph have not this condition deg(u) + deg(v) >= n as true will not have a hamiltonian circuit. Ex. A cycle graph with n = 6 will have hamiltonian circuit.

4. Edge-disjoint hamiltonian circuit : Hamiltonian circuit which doesn't have any common edge with other hamiltonian circuit in same graph.
In complete graph for n = 3. We have only one hamiltonian circuit. (3-1)/2 = 1.
For n = 4. We have 6 edges in complete graph. Suppose in one hamiltonian cycle you include e1, e2, e3, e4 edges. Now we have e5 and e6 edge left we can't for another hamiltonian cycle with this edge. So again one.
(4 - 1)/ 2 = 1.

So Answer: C.

Comments

Unable to understand point 4 well

---

@sachin Point 4 is Finding the edge disjoint hamiltonian cycle. Edge disjoint means hamiltonian cycle which don't have common edges.
For a complete graph the no. of edge disjoint hamiltonian cycle is given by floor( (n-1)/ 2). where n is the no. of vertices in complete graph.
Put n = 5. We got floor ((5-1)/2) = 2. Now draw K5 you will find two edge disjoint hamiltonian cycle.

---

Here's my intuition :

I understand that each vertex has a degree of 'n-1' and if we divide the incident edges on a vertex into groups of 2, we can utilize each group once, for coming in and going out from that vertex. my question is why the number of edge-disjoint hamiltonian cycle is (n-1) /2, I mean can't I include all the cyclic permutation corresponding to each edge-disjoint hamiltonian cycle into consideration which would give more than (n-1)/2.

I know it's a bit too late to respond to this question I hope somebody can follow up and tell where my thinking is going wrong?