UGC NET CS 2015 Jun- paper-2
October 16, 2023UGC NET CS 2015 Jun- paper-2
October 16, 2023UGC NET CS 2015 Jun- paper-2
|
Question 5
|
Consider a Hamiltonian Graph (G) with no loops and parallel edges. Which of the following is true with respect to this Graph (G) ?
(a) deg (v) ≥ n / 2 for each vertex of G
(b) |E(G)| ≥ 1 / 2 (n – 1) (n – 2) + 2 edges
(c) deg (v) + deg (w) ≥ n for every n and v not connected by an edge.
(a) deg (v) ≥ n / 2 for each vertex of G
(b) |E(G)| ≥ 1 / 2 (n – 1) (n – 2) + 2 edges
(c) deg (v) + deg (w) ≥ n for every n and v not connected by an edge.
|
(a) and (b)
|
|
|
(b) and (c)
|
|
|
(a) and (c)
|
|
|
(a), (b) and (c)
|
Question 5 Explanation:
→ According to Dirac’s theorem on Hamiltonian cycles, the statement that an n-vertex graph in which each vertex has degree at least n/2 must have a Hamiltonian cycle.
→ According to ore’s theorem,Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore’s theorem states that if deg v + deg w ≥ n for every pair of distinct non adjacent vertices v and w of G, then G is Hamiltonian.
→ A complete graph G of n vertices has n(n−1)/2 edges and a Hamiltonian cycle in G contains n edges. Therefore the number of edge-disjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edge-disjoint Hamiltonian cycles.
So the statement(b) is false and statement a and c are true.
→ According to ore’s theorem,Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore’s theorem states that if deg v + deg w ≥ n for every pair of distinct non adjacent vertices v and w of G, then G is Hamiltonian.
→ A complete graph G of n vertices has n(n−1)/2 edges and a Hamiltonian cycle in G contains n edges. Therefore the number of edge-disjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edge-disjoint Hamiltonian cycles.
So the statement(b) is false and statement a and c are true.
Correct Answer: C
Question 5 Explanation:
→ According to Dirac’s theorem on Hamiltonian cycles, the statement that an n-vertex graph in which each vertex has degree at least n/2 must have a Hamiltonian cycle.
→ According to ore’s theorem,Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore’s theorem states that if deg v + deg w ≥ n for every pair of distinct non adjacent vertices v and w of G, then G is Hamiltonian.
→ A complete graph G of n vertices has n(n−1)/2 edges and a Hamiltonian cycle in G contains n edges. Therefore the number of edge-disjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edge-disjoint Hamiltonian cycles.
So the statement(b) is false and statement a and c are true.
→ According to ore’s theorem,Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore’s theorem states that if deg v + deg w ≥ n for every pair of distinct non adjacent vertices v and w of G, then G is Hamiltonian.
→ A complete graph G of n vertices has n(n−1)/2 edges and a Hamiltonian cycle in G contains n edges. Therefore the number of edge-disjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edge-disjoint Hamiltonian cycles.
So the statement(b) is false and statement a and c are true.
Subscribe
Login
0 Comments