1 Advanced Mathematics • Graph Theory In a graph, the number of vertices with odd degrees is always: In a graph, the number of vertices with odd degrees is always: सेव करें Save सेव्ड Saved A. Odd Odd B. Zero Zero C. Even Even D. Cannot be determined Cannot be determined उत्तर और व्याख्या देखें Show answer and explanation सही उत्तर: C Correct Answer: C By the handshaking lemma, the sum of all vertex degrees is even. Therefore, vertices of odd degree must occur in an even number. By the handshaking lemma, the sum of all vertex degrees is even. Therefore, vertices of odd degree must occur in an even number.
2 Advanced Mathematics • Graph Theory If every point of G has even degree, then G is a: If every point of G has even degree, then G is a: सेव करें Save सेव्ड Saved A. Planar Graph Planar Graph B. Tree Tree C. Eulerian Graph Eulerian Graph D. Pie Chart Pie Chart उत्तर और व्याख्या देखें Show answer and explanation सही उत्तर: C Correct Answer: C A connected graph has an Euler circuit if and only if every vertex has even degree; hence it is Eulerian. A connected graph has an Euler circuit if and only if every vertex has even degree; hence it is Eulerian.
3 Advanced Mathematics • Graph Theory Circumference of a cyclic graph is defined as: Circumference of a cyclic graph is defined as: सेव करें Save सेव्ड Saved A. Twice the sum of its total degree Twice the sum of its total degree B. Length of the longest cycle Length of the longest cycle C. Length of the shortest cycle Length of the shortest cycle D. Thrice the sum of its total degree Thrice the sum of its total degree उत्तर और व्याख्या देखें Show answer and explanation सही उत्तर: B Correct Answer: B The circumference of a graph is the length, measured by number of edges, of its longest cycle. The circumference of a graph is the length, measured by number of edges, of its longest cycle.
4 Advanced Mathematics • Graph Theory What is the number of edges present in a complete graph with n vertices? What is the number of edges present in a complete graph with n vertices? सेव करें Save सेव्ड Saved A. n(n - 1) n(n - 1) B. n^2/2 n^2/2 C. n(n + 1)/2 n(n + 1)/2 D. n(n - 1)/2 n(n - 1)/2 उत्तर और व्याख्या देखें Show answer and explanation सही उत्तर: D Correct Answer: D Every unordered pair of distinct vertices forms exactly one edge, so the number of edges is C(n,2) = n(n - 1)/2. Every unordered pair of distinct vertices forms exactly one edge, so the number of edges is C(n,2) = n(n - 1)/2.
5 Advanced Mathematics • Graph Theory A graph G with p vertices (p >= 3) is Hamiltonian if: A graph G with p vertices (p >= 3) is Hamiltonian if: सेव करें Save सेव्ड Saved A. For all vertices v in G, degree(v) < p/2 For all vertices v in G, degree(v) < p/2 B. For all vertices v in G, degree(v) >= p/2 For all vertices v in G, degree(v) >= p/2 C. All vertices v in G have an even degree All vertices v in G have an even degree D. All vertices in G have an odd degree All vertices in G have an odd degree उत्तर और व्याख्या देखें Show answer and explanation सही उत्तर: B Correct Answer: B By Dirac's theorem, a simple graph with p >= 3 vertices is Hamiltonian if every vertex has degree at least p/2. By Dirac's theorem, a simple graph with p >= 3 vertices is Hamiltonian if every vertex has degree at least p/2.
6 Advanced Mathematics • Graph Theory For a tree with q lines, the number of vertices p equals: For a tree with q lines, the number of vertices p equals: सेव करें Save सेव्ड Saved A. 2q 2q B. q q C. q + 2 q + 2 D. q + 1 q + 1 उत्तर और व्याख्या देखें Show answer and explanation सही उत्तर: D Correct Answer: D A tree with p vertices has exactly p - 1 edges. Therefore, if the number of lines or edges is q, then p = q + 1. A tree with p vertices has exactly p - 1 edges. Therefore, if the number of lines or edges is q, then p = q + 1.
7 Advanced Mathematics • Graph Theory Every n-connected graph with p vertices has at least: Every n-connected graph with p vertices has at least: सेव करें Save सेव्ड Saved A. pn/2 lines pn/2 lines B. n(p + 1)/2 lines n(p + 1)/2 lines C. pn lines pn lines D. 2pn lines 2pn lines उत्तर और व्याख्या देखें Show answer and explanation सही उत्तर: A Correct Answer: A An n-connected graph has minimum degree at least n. By the handshaking lemma, twice the number of edges is at least pn, so it has at least pn/2 edges. An n-connected graph has minimum degree at least n. By the handshaking lemma, twice the number of edges is at least pn, so it has at least pn/2 edges.
8 Advanced Mathematics • Graph Theory Maximum point connectivity of a graph G with p vertices and q edges, where q>=p-1, is: Maximum point connectivity of a graph G with p vertices and q edges, where q>=p-1, is: सेव करें Save सेव्ड Saved A. q-1 q-1 B. q+1 q+1 C. 2q/p 2q/p D. q/p q/p उत्तर और व्याख्या देखें Show answer and explanation सही उत्तर: C Correct Answer: C The sum of all vertex degrees is 2q, so the average degree is 2q/p. Consequently the maximum degree is at least the average; option C is the result marked in the source. The sum of all vertex degrees is 2q, so the average degree is 2q/p. Consequently the maximum degree is at least the average; option C is the result marked in the source.