Graph Theory MCQ Test 1

1. In graph theory, what does a 'cycle' refer to?

2. What does the term 'adjacent' mean in the context of graph theory?

3. In graph theory, what is the chromatic number of a cycle graph with 'n' vertices?

4. Which graph theory problem involves finding a subgraph that is both a tree and a spanning subgraph of a given graph?

5. In a weighted graph, what does the weight of an edge represent?

6. What is the term used for a graph that can be drawn in such a way that no edges cross each other?

7. What is the term used for a graph in which there is an edge between every pair of vertices?

8. Which graph theory problem deals with finding a sequence of vertices such that each consecutive pair forms an edge?

9. Which of the following is a graph where every edge is directed from one vertex to another?

10. Which graph theory problem involves finding a path that visits every vertex exactly once?

11. Which of the following is a type of graph where every node is connected to every other node?

12. What is the term used for a graph that has a path from every vertex to every other vertex but not necessarily a closed path?

13. What does a Hamiltonian cycle in a graph refer to?

14. In graph theory, what does a 'cut edge' refer to?

15. What is the basic definition of a graph in graph theory?

16. What is the maximum number of edges in a simple graph with 5 vertices?

17. What is the term used for a graph that has exactly one vertex of odd degree?

18. In a directed graph, what are edges typically called?

19. What is the edge connectivity of a complete graph with 'n' vertices?

20. Which theorem states that if every vertex of a graph has even degree, then the graph has a closed Eulerian trail?

21. Which of the following statements about Eulerian graphs is true?

22. Which of the following is a property of a planar graph?

23. Which graph theory problem involves finding the shortest path from a source vertex to all other vertices in a weighted graph?

24. What is the edge chromatic number of a complete graph with 'n' vertices?

25. Which of the following properties does a complete bipartite graph possess?

26. Which theorem states that every connected finite simple graph with at least two vertices has a vertex of degree at most 1?

27. What is the term used for a graph where all vertices have the same degree?

28. What is the maximum number of edges in an acyclic graph with 'n' vertices?

29. What does a spanning tree of a connected graph mean?

30. In graph theory, what does 'forest' refer to?

31. What is the term used for a path in a graph that starts and ends at the same vertex and visits every vertex exactly once?

32. Which of the following properties does a graph possess if it can be drawn in such a way that no edges intersect each other?

33. What is the minimum number of edges in a connected graph with 'n' vertices?

34. In a tree, what is the term used for a vertex with degree 1?

35. Which theorem states that the sum of the degrees of all vertices in a graph is twice the number of edges?

36. What is the term used for a graph that contains no cycles?

37. What is the term used for a graph in which the edges have a direction?

38. Which of the following is true about a tree?

39. Which of the following algorithms is used to find the minimum spanning tree of a graph?

40. What is the chromatic number of a complete graph with 'n' vertices?

41. Which of the following properties does a bipartite graph possess?

42. Which theorem states that in any graph, the sum of the degrees of all vertices is twice the number of edges?

43. What does the matrix tree theorem relate to in graph theory?

44. Which of the following is a graph with vertices divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set?

45. What is the term used for a subgraph that contains all the vertices of the original graph and is also a tree?

46. What is the term used for a cycle in a directed graph that traverses each edge exactly once?

47. In a graph, what does a 'bridge' refer to?

48. Which algorithm is used to find the shortest path in a weighted graph where some of the edge weights may be negative?

49. Which graph theory problem involves finding a subset of vertices such that every edge in the graph has at least one of its endpoints in the subset?

50. Which graph theory problem deals with finding the smallest number of vertices that cover all the edges in a graph?