4.1.1 - Introduction to Graph Theory.

1. What is a graph composed of?

(A) Only vertices
(B) Only edges
(C) Vertices and edges
(D) Nodes and links

Correct Answer: (C) Vertices and edges

2. In the notation G=(V,E), what does V represent?

(A) A set of edges
(B) A set of vertices
(C) A set of nodes
(D) A set of links

Correct Answer: (B) A set of vertices

3. In the notation G=(V,E), what does E represent?

(A) A set of vertices
(B) A set of edges
(C) A set of nodes
(D) A set of points

Correct Answer: (B) A set of edges

4. What is the term for the number of vertices in a graph?

(A) Size of the graph
(B) Order of the graph
(C) Cardinality of edges
(D) Number of links

Correct Answer: (B) Order of the graph

5. What is the term for the number of edges in a graph?

(A) Size of the graph
(B) Order of the graph
(C) Cardinality of vertices
(D) Number of nodes

Correct Answer: (A) Size of the graph

6. How are edges in a graph represented?

(A) As ordered pairs of vertices
(B) As unordered pairs of vertices
(C) As a single vertex
(D) As a single node

Correct Answer: (B) As unordered pairs of vertices

7. What are the end vertices of an edge in a graph called?

(A) Nodes
(B) Points
(C) End vertices
(D) Links

Correct Answer: (C) End vertices

8. If V(G)={v₁,v₂,…,v_n} and E(G)={e₁,e₂,…,e_m}, what does each e_k represent?

(A) An unordered pair of vertices
(B) An ordered pair of vertices
(C) A single vertex
(D) A set of nodes

Correct Answer: (A) An unordered pair of vertices

9. What does the cardinality of V denote in a graph?

(A) The number of edges
(B) The number of vertices
(C) The number of nodes
(D) The number of links

Correct Answer: (B) The number of vertices

10. What does the cardinality of E denote in a graph?

(A) The number of vertices
(B) The number of edges
(C) The number of nodes
(D) The number of points

Correct Answer: (B) The number of edges

11. How is an edge typically represented in a graph?

(A) As a single vertex
(B) As an ordered pair of vertices
(C) As an unordered pair of vertices
(D) As a single node

Correct Answer: (C) As an unordered pair of vertices

12. In a graph, if e_k={v_i,v_j}, what are v_i and v_j?

(A) Vertices not connected by e_k
(B) End vertices of the edge e_k
(C) Edges connecting v_i and v_j
(D) Nodes in the graph

Correct Answer: (B) End vertices of the edge e_k

13. Which term is used for the objects in a graph that are joined by edges?

(A) Edges
(B) Vertices
(C) Nodes
(D) Points

Correct Answer: (B) Vertices

14. What term is used for the connections between vertices in a graph?

(A) Vertices
(B) Edges
(C) Nodes
(D) Links

Correct Answer: (B) Edges

15. In graph theory, what is the number of vertices in a graph called?

(A) Size
(B) Order
(C) Cardinality of edges
(D) Number of links

Correct Answer: (B) Order

16. In graph theory, what is the number of edges in a graph called?

(A) Size
(B) Order
(C) Cardinality of vertices
(D) Number of points

Correct Answer: (A) Size

17. How is the set of edges denoted in a graph?

(A) V
(B) E
(C) N
(D) P

Correct Answer: (B) E

18. How is the set of vertices denoted in a graph?

(A) E
(B) V
(C) N
(D) P

Correct Answer: (B) V

4.1.2 - Simple Graphs, Multigraphs, Complete Graphs and Bigraphs.

19. What defines a simple graph?

(A) A graph with parallel edges and self-loops
(B) A graph with only one edge connecting each pair of vertices
(C) A graph with multiple pathways leading to a single destination
(D) A graph with loops and multiple edges

Correct Answer: (B) A graph with only one edge connecting each pair of vertices

20. Which type of graph allows multiple edges between the same pair of vertices but no self-loops?

(A) Simple Graph
(B) Complete Graph
(C) Multigraph
(D) Bigraph

Correct Answer: (C) Multigraph

21. What are parallel edges in a multigraph?

(A) Edges that connect two different pairs of vertices
(B) Edges that connect the same pair of vertices
(C) Edges that connect a vertex to itself
(D) Edges that do not connect any vertices

Correct Answer: (B) Edges that connect the same pair of vertices

22. What is a loop in the context of a multigraph?

(A) An edge that connects two different vertices
(B) An edge that connects a vertex to itself
(C) A graph with no edges
(D) A set of parallel edges connecting multiple vertices

Correct Answer: (B) An edge that connects a vertex to itself

23. How is a complete graph defined?

(A) A graph with no edges
(B) A graph where each vertex is connected to every other vertex
(C) A graph with parallel edges
(D) A graph with self-loops and no connections between vertices

Correct Answer: (B) A graph where each vertex is connected to every other vertex

24. What is the representation of a complete graph with _n vertices?

(A) _K_n
(B) _M_n
(C) _G_n
(D) _B_n

Correct Answer: (A) _K_n

25. What does a bigraph consist of?

(A) A single set of vertices and edges
(B) Two orthogonal structures: place graph and link graph
(C) A graph with only parallel edges
(D) A graph with no vertices

Correct Answer: (B) Two orthogonal structures: place graph and link graph

26. In a bigraph, what does the place graph describe?

(A) Non-local hyperlinks between entities
(B) The nesting of entities, such as a phone inside a room
(C) The degree of vertices
(D) The connections between vertices and edges

Correct Answer: (B) The nesting of entities, such as a phone inside a room

27. What does the link graph in a bigraph provide?

(A) Internal connections within a single entity
(B) Non-local hyperlinks between entities
(C) The degree of vertices within the same entity
(D) Only parallel edges between vertices

Correct Answer: (B) Non-local hyperlinks between entities

28. How are bi-graphs considered in terms of compositional structures?

(A) They cannot be composed into larger structures
(B) They are compositional, meaning they can be built from smaller bi-graphs
(C) They only include parallel edges
(D) They are single, non-composable structures

Correct Answer: (B) They are compositional, meaning they can be built from smaller bi-graphs

4.1.3 - Degree of a Vertex.

29. What does the degree of a vertex in a graph represent?

(A) The number of vertices in the graph
(B) The number of edges incident with the vertex
(C) The maximum distance from the vertex
(D) The total number of self-loops in the graph

Correct Answer: (B) The number of edges incident with the vertex

30. How is the degree of a vertex denoted?

(A) d(v)
(B) deg(v)
(C) Δ(v)
(D) Indeg(v)

Correct Answer: (B) deg(v)

31. In a basic network with n vertices, what is the degree of any vertex v?

(A) 0
(B) n
(C) n-1
(D) 1

Correct Answer: (C) n-1

32. What is the minimum degree of vertices in V(G) denoted by?

(A) deg(v)
(B) d(G)
(C) ∆(G)
(D) indeg(v)

Correct Answer: (B) d(G)

33. What does the maximum degree of vertices in V(G) denote?

(A) d(G)
(B) deg(v)
(C) ∆(G)
(D) outdeg(v)

Correct Answer: (C) ∆(G)

34. In the graph example provided, what is the degree of vertex 'e'?

(A) 2
(B) 1
(C) 0
(D) 4

Correct Answer: (C) 0

35. What is an isolated vertex?

(A) A vertex connected to all other vertices
(B) A vertex with no incident edges
(C) A vertex that has a self-loop
(D) A vertex with the maximum degree

Correct Answer: (B) A vertex with no incident edges

36. In a directed graph, what is the indegree of a vertex?

(A) The number of edges leaving the vertex
(B) The number of edges entering the vertex
(C) The total number of vertices in the graph
(D) The total number of self-loops

Correct Answer: (B) The number of edges entering the vertex

37. How is the outdegree of a vertex denoted in a directed graph?

(A) deg−(V)
(B) deg+(V)
(C) indeg(V)
(D) d(V)

Correct Answer: (B) deg+(V)

38. Which of the following statements is true about the degree of a vertex?

(A) It can only be negative.
(B) Each self-loop is counted once.
(C) The degree is always a positive number.
(D) Indegree and outdegree are the same.

Correct Answer: (C) The degree is always a positive number.

4.1.4 - Isomorphic Graphs, Euler Graphs, Hamiltonian Graphs, Bipartite Graphs and Complete Bipartite Graphs.

39. What defines a bipartite graph?

(A) It has vertices of the same degree
(B) Vertices can be divided into two distinct sets
(C) It contains only one vertex
(D) All edges are self-loops

Correct Answer: (B) Vertices can be divided into two distinct sets

40. In a graph G, what is an Euler line?

(A) A path that visits every vertex exactly once
(B) A closed walk containing all the edges exactly once
(C) A line connecting two vertices
(D) A path that visits each vertex multiple times

Correct Answer: (B) A closed walk containing all the edges exactly once

41. What is an isomorphic graph?

(A) A graph that contains a cycle
(B) A graph that can be transformed into another by renaming vertices
(C) A graph with all vertices of odd degree
(D) A disconnected graph

Correct Answer: (B) A graph that can be transformed into another by renaming vertices

42. A Hamiltonian cycle in a graph G is:

(A) A cycle visiting each vertex exactly once
(B) A path that visits all edges
(C) A cycle visiting some vertices multiple times
(D) A path that does not return to the starting vertex

Correct Answer: (A) A cycle visiting each vertex exactly once

43. When does a connected graph G have an Euler circuit?

(A) All vertices must have odd degree
(B) At least one vertex must have even degree
(C) All vertices must have even degree
(D) It must be a bipartite graph

Correct Answer: (C) All vertices must have even degree

44. Which of the following is true about a complete bipartite graph \( K_{m,n} \)?

(A) Every vertex in one set is connected to every vertex in the other set
(B) It has no edges
(C) It contains at least one cycle
(D) All vertices are in a single set

Correct Answer: (A) Every vertex in one set is connected to every vertex in the other set

45. What condition must be met for a graph to be classified as an Euler graph?

(A) It must be disconnected
(B) All vertices have even degree
(C) All vertices have odd degree
(D) It must contain at least one Hamiltonian cycle

Correct Answer: (B) All vertices have even degree

46. If a graph has 24 edges and each vertex has a degree of 4, how many vertices does it have?

(A) 12
(B) 8
(C) 10
(D) 16

Correct Answer: (A) 12

47. What is a Hamiltonian path?

(A) A path that visits all vertices exactly once
(B) A path that visits some vertices multiple times
(C) A path that does not return to the starting vertex
(D) A path that includes all edges

Correct Answer: (A) A path that visits all vertices exactly once

48. Which of the following is an example of an isomorphic graph?

(A) A graph with different number of edges
(B) A graph that has the same number of vertices and edges but different structures
(C) A graph that is a complete graph
(D) A graph that is a tree

Correct Answer: (B) A graph that has the same number of vertices and edges but different structures

49. How can you determine if two graphs are isomorphic?

(A) By counting the number of edges
(B) By comparing the degrees of corresponding vertices
(C) By checking if they have the same number of vertices only
(D) By ensuring all edges are self-loops

Correct Answer: (B) By comparing the degrees of corresponding vertices

50. Which property is true for a complete bipartite graph \( K_{m,n} \)?

(A) All vertices have odd degree
(B) It has edges only within a set
(C) Every vertex in set \( V_1 \) is connected to every vertex in set \( V_2 \)
(D) It has no vertices

Correct Answer: (C) Every vertex in set \( V_1 \) is connected to every vertex in set \( V_2 \)

51. A graph is said to be Eulerian if:

(A) It has at least one vertex of odd degree
(B) All vertices have even degree and the graph is connected
(C) It has no edges
(D) It contains at least one cycle

Correct Answer: (B) All vertices have even degree and the graph is connected

52. Which of the following statements is true regarding Hamiltonian graphs?

(A) They must have all vertices of odd degree
(B) They may contain multiple Hamiltonian paths
(C) They must contain at least one Eulerian circuit
(D) They have no cycles

Correct Answer: (B) They may contain multiple Hamiltonian paths

53. In the context of Euler graphs, what is a necessary condition for a graph to contain an Euler path?

(A) It must be connected and have at most two vertices of odd degree
(B) All vertices must have even degree
(C) It must have a Hamiltonian cycle
(D) It must be a complete graph

Correct Answer: (A) It must be connected and have at most two vertices of odd degree