Subject: Discrete Math

Topics can be :

1. Algebraic Structures (Abstract Algebra, Binary structures) 2. Graph Theory 3. Graph Theory (Special graphs and Trees) 4. Graph Theory Problems and Applications

LETTERS ONLY

For Items 18-22, refer to the incidence table below: E1 E2 E3 E4 A -1 B 0 -1 - 1 C 0 -1 0 0 -1 0 - 1 F 0 3 18. Which of the following statements is/are TRUE? 1. The graph is a strongly connected graph. I. The graph is not a multigraph A. I only is true C. Both I and Il are true B. II only is true D. Neither I nor II is true 19.Which of the following statements is/are TRUE? 1. ACDDDEB is a valid walk. 1I. ABDE is a valid path. A. I only is true C. Both I and Il are true B. II only is true D. Neither I nor II is true 20. The vertex with the highest in-degree is A. Vertex A C. Vertex C B. Vertex B D. Vertex D 21. What is the diameter of the graph? A. 1 C. 3 B. 2 D. 4 22. Which of the following statements is/are TRUE? A. Edge E3 is incident from D B. Edge E3 is incident from A C. Edge E3 is incident from both A and B D. None of the above 23. Which of the following is/are true among the graphs A, B, and C? Graph A Co 3 Graph B Graph C A. Only Graph B is a subgraph of A B. Only Graph C is a subgraph of A C. Both B and C are a subgraph of A D. Neither B nor C is a subgraph of A 24. Which of the following statements is/are TRUE? 1. The upper triangle of an adjacenty matrix of a simple undirected graph is enough to describe a graph 1I. The lower triangle of an adjacenty matrix of a simple undirected graph is enough to describe a graph A. I only is true C. Both I and Il are true B. II only is true D. Neither I nor II is true D F EFor Items 25-30, choose what mulescribes the sequence of vertices based on the graph abatre. A. Not a walk A trail only but not a path . A path only . A walk only A circuit only A cycle only . An Eulerian Circuit H. A Hamiltonian Cycle B C D E F. G 25. ABCDEFG 26. DCBFED 27 ABAFGCEDA 28. BAFEGCEDCBFGB 29. GECGBFG 30. AFGCE 31 .All of the following graphs are planar Except for: A. The complete bipartite graph K14 B. The 5 vertices 4-regular graph C. The complete graph K. D. The wheel graph W1.J 32.Al| of the following graphs are Eulerian graphs Except for. A. a 6-regular graph C. a cycle graph B. the complete graph K, D. a path graph 33.Which of the following statements isIare TRUE? l. Adding edge to a path graph will always result in a cycle graph. it. A graph with six vertices and four edges always forms a tree. A. | only is true C. Both I and II are the B. It only is true D. Neither I nor II are true 34.Which of the following statements islare TRUE? l. Given a rooted tree that includes nodes A and D, ifnode D is the parent of node A, then the height of node A is lower than that of node D. ll. An empty graph is an example of a forest. A. | only is true C. Both l and II are true B_ u only is true D. Neither I nor II are true 35.Which of the fol|0wing statement; islare TRUE? 1. The height of the root of a tree is equal to the level of the root. ll. All cycle graphs are homeomorphic to each other. A. | only is true C. Both I and II are the B. It only is true D. Neither I nor II are true 36.What is the size of the special graph Km? A. mm C. m - n B. 2(m+n) D. 2(n-1) 37. Consider Graph A and B are isomorphic. If Vertex A of Graph A corresponds to vertex 3 in Graph 3, which of the vertices in Graph B conesponds to vertex E in Graph A? 0 0 7 ~ 'v'o "e Grlph A Graph 8 A. Vertex 1 B. Vertex 4 C. Vertex 2 D. Vertex 5