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) \geq n/2\) for each vertex of G (b) \(|E(G)| \geq 1/2\ (n-1)(n-2)+2\) edges (c) deg \((v)\) + deg \((w) \geq n\) for every \(v\) and \(w\) not connected by an edge
(a) and (c)
Statement (a) is Dirac's condition: in a simple graph on \(n \geq 3\) vertices, every vertex having degree at least \(n/2\) gives a Hamiltonian cycle.
Statement (c) is Ore's condition: \(\deg(v)+\deg(w) \geq n\) for every non-adjacent pair also gives a Hamiltonian cycle, and it generalises Dirac's condition.
These two vertex-degree conditions are the classical results tied to Hamiltonian graphs, while (b) is an edge-count bound rather than a degree condition.
Hence, (a) and (c).
Similar Questions
A tree with n vertices is called graceful, if its vertices can be labelled with integers 1, 2,....n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are graceful ?
Codes :
Consider the graph given below :
The two distinct sets of vertices, which make the graph bipartite are :
Which of the following statement(s) is/are false ?
(a) A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
(b) A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
(c) A complete graph \((K_{n})\) has a Hamilton Circuit whenever \(n \geq 3\).
(d) A cycle over six vertices \((C_{6})\) is not a bipartite graph but a complete graph over 3 vertices is bipartite.
Codes :
Consider the following statements :
(a) Depth - first search is used to traverse a rooted tree.
(b) Pre - order, Post-order and Inorder are used to list the vertices of an ordered rooted tree.
(c) Huffman’s algorithm is used to find an optimal binary tree with given weights.
(d) Topological sorting provides a labelling such that the parents have larger labels than their children.
Which of the above statements are true ?
Consider a complete bipartite graph \(k_{m,n}\). For which values of m and n does this, complete graph have a Hamilton circuit
Consider the graph given below as :
Which one of the following graph is isomorphic to the above graph ?
Arrange the following graph on the basis of number of edges in increasing order [for n = 4]
A. Kn (Complete Graph)
B. Cn (Cycle graph)
C. Wn (Wheel graph)
D. Kn,n (Complete Bipartite Graphs)
E. Qn (n-cubes graph)
Choose the correct answer from the options given below:
A graph G with number of vertices greater and equal than three i.e. (n ≥ 3) is a Hamiltonian graph, if the degree of each vertex is greater and equal to . . . .
Let ‘G’ be a simple, undirected graph with n (n>10) vertices and ‘k’ connected components. What is the minimum possible number of edges of ‘G’?
Let G(V, E) be an undirected graph with l edges. Then the sum of degree of all vertices is equal to ________.
Important Questions from Graph Theory
A principal node is a
Which of the following statement(s) is/are correct regarding about the undirected graph?
I. Number of odd degree vertices is even.
II. Sum of degrees of all vertices is even.
Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v)$, $u, v \in V$ such that $u \neq v$, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given options is CORRECT for every such graph G?
- Maintaining a graph in memory by means of its adjacency matrix is known as
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on plane is equal to_________.
