Understanding Graph Theory

What is a graph in graph theory?

• A type of function plot

• A chart used in statistics

• A 3D model in computer graphics

• A collection of vertices and edges

What does it mean if a graph is 'complete'?

• It has an edge from every vertex to every other vertex

• It is fully colored

• It contains no edges

• It only has vertices and no edges

What is an 'empty graph'?

• A graph with only one vertex

• A graph that is not connected

• A graph with vertices but no edges

• A graph with no vertices and no edges

What is the 'order' of a graph?

• The maximum degree of the graph

• The number of vertices in the graph

• The number of edges in the graph

• The sequence of vertices

What is a 'directed graph'?

• A graph where each edge has a direction

• A graph where edges are bidirectional

• A graph with no directions on edges

• A graph that can only be drawn straight

What does 'isomorphic' mean in the context of graphs?

• Two graphs having the same structure

• Graphs that are colored the same

• Graphs that are completely different

• Graphs that have identical vertices

What is a 'tree' in graph theory?

• A directed graph with one way edges

• An undirected graph with no cycles

• A complete graph

• A graph with only one vertex

What is an Eulerian path?

• A path that starts and ends at the same vertex

• A path that can be traversed in both directions

• A path that visits every vertex once

• A path that crosses every edge exactly once

What challenge did Euler solve about the Koenigsberg bridges?

• Calculated the shortest path across all bridges

• Designed new bridges to make the path possible

• Found a path that crossed each bridge twice

• Proved that a path crossing each bridge once is impossible unless each vertex has an even degree

What is a Hamiltonian path?

• A path that includes at least one cycle

• A path that uses the shortest possible route

• A path that crosses each edge exactly once

• A path that visits each vertex exactly once