5.1 Graph Theory

• What is a graph formally defined as in graph theory?

  G = (V, E)
• Vertices in a graph are also called nodes.

  True
• What does it mean if two vertices are adjacent in a graph?

  They are connected by an edge
• In an undirected graph, edges represent two-way relationships between vertices.
• What type of relationships do edges in a directed graph represent?

  One-way relationships
• In a directed graph, edges have a specific direction
• In a directed graph, edges represent one-way relationships between vertices
• What type of graph has no cycles?

  Tree
• What is the term for two vertices connected by an edge?

  Adjacent
• What are vertices in a graph also called?

  Nodes
• What are edges in a graph?

  Connections between vertices
• What does the degree of a vertex in a graph refer to?

  Number of edges connected
• Cycles in graphs indicate the presence of redundant connections
• Match the graph component with its definition:

  Path ↔️ Sequence of connected vertices

  Cycle ↔️ Path that starts and ends at the same vertex

  Tree ↔️ Connected graph with no cycles
• Match the graph type with its description:

  Bipartite Graph ↔️ Vertices divided into two disjoint sets

  Directed Graph ↔️ Edges have a specific direction

  Tree ↔️ Connected graph with no cycles
• Road networks are examples of Eulerian graphs.


  True
• Euler's formula for planar graphs states: v - e + f = 2


  True
• For a planar graph, Euler's formula states that V - E + F = 2
• Isomorphic graphs must have the same number of vertices.

  True
• Steps to determine if two graphs are isomorphic:

  1️⃣ Check if the number of vertices is the same

  2️⃣ Check if the number of edges is the same

  3️⃣ Verify that the degree sequences are identical

  4️⃣ Establish a bijective function between vertices

  5️⃣ Confirm that adjacency is preserved
• Match the graph property with its definition:

  Vertices ↔️ The individual points in a graph

  Edges ↔️ The lines connecting vertices
• Match the graph type with its property:

  Directed graph ↔️ Edges have a specific direction

  Undirected graph ↔️ Edges have no direction
• Edges in a directed graph represent one-way relationships between vertices


  True
• What does the symbol 'E' represent in graph theory?

  Edges
• The number of edges connected to a vertex is called its degree
• Trees are graphs with no cycles
• Bipartite graphs are used to model problems like job-applicant matching
• Match the graph type with its description:

  Bipartite Graph ↔️ Vertices divided into two disjoint sets

  Directed Graph ↔️ Edges have a specific direction

  Undirected Graph ↔️ Edges have no direction

  Tree ↔️ Connected graph with no cycles
• What is the defining property of a Hamiltonian graph?

  Closed path visits each vertex once
• In a graph, V represents the set of vertices
• The number of edges connected to a vertex is called its degree
• Edges in an undirected graph have a specific direction.

  False
• Edges in an undirected graph represent two-way relationships between vertices
• What type of relationship do edges in a directed graph represent?

  One-way
• What is an example of a system that can be modeled using an undirected graph?

  Social network
• Edges in a graph connect vertices to each other.


  True
• In an undirected graph, edges represent two-way relationships between vertices
• What is a graph in mathematical terms?

  Vertices and edges
• Two vertices are adjacent if they are connected by an edge
• A cycle in a graph is a path where the first and last vertices are the same.

  True