UGC NET CSE | Junet 2015 | Part 2 | Question: 5

Question

Consider a Hamiltonian Graph(G) with no loops and parallel edges. Which of the following is true with respect to this graph (G)?

1. $\deg (v) \geq n/2$ for each vertex of $G$
2. $\mid E(G) \mid \geq 1/2 (n-1)(n-2)+2$ edges
3. $\deg(v) + \deg(w) \geq n$ for every $v$ and $\omega$ not connected by an edge

 

• A. $i$ and $ii$
• B. $ii$ and $iii$
• C. $i$ and $iii$
• D. $i$, $ii$, and $iii$

Answer 1

All statements are TRUE

answer D

Please remember Dirac theorem  (https://en.wikipedia.org/wiki/Dirac%27s_theorem)

 if each vertex has deg(v)≥n/2, then the graph has a Hamilton circuit (Dirac's Theorem).

Comments

The theorem says if every vertex has degree greater then or equal to n/2, then the graph is Hamiltonian.
But the question is other way round, We have a hamiltonian graph and we need to tell whether deg (v) >= n/2 for each vertex of G.

Consider a hexagon. the statement fails !!

@Arjun Please clarify

Answer 2

Hamiltonian Graph(G) with no loops and parallel edges.

a. deg (v) >= n/2 for each vertex of G  [Dirac Theorem]

c. deg(v) + deg(w) >= n fr every v and ω not connected by an edge [Ore"s Theorem]

B. also true

so D is ans

 

Comments

How is B true. Can you plz explain

---

Draw a cycle graph with 10 nodes. It is hamiltonian. But all three condition fails. I think the question is wrong.

Answer 3

In an Hamiltonian Graph (G) with no loops and parallel edges:
According to Dirac's theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.
According to Ore's theorem deg (v) + deg (w) ≥ n for every n and v not connected by an edge is sufficient condition for a graph to be hamiltonian.
If |E(G)| ≥ 1 / 2 * [(n - 1) (n - 2)] then graph is connected but it doesn't guaranteed to be Hamiltonian Graph.
(a) and (c) is correct regarding to Hamiltonian Graph.
So, option (C) is correct.

source-gfg