1 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: 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 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: 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 Mathematics • Graph Theory Circumference of a cyclic graph is defined as: Circumference of a cyclic graph is defined as: 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 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? 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 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: 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 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: 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 Mathematics • Graph Theory Every n-connected graph with p vertices has at least: Every n-connected graph with p vertices has at least: 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 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: 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.