An airline network has three direct flights between Chicago and New York operated by different carriers. Which graph model best captures this situation?
AA simple graph, since Chicago and New York are distinct vertices
BA directed graph, since flights operate in both directions
CA multigraph, since multiple distinct edges between the same pair of vertices are needed
DA weighted simple graph with the weight set to 3
A simple graph allows at most one edge between any pair of vertices, so it cannot represent three separate routes between the same two cities. A weighted graph with weight 3 captures total capacity but loses the identity of the individual routes. A multigraph is the right choice because it explicitly allows multiple edges between the same pair of vertices — each edge is a distinct connection with potentially different properties. The choice of definition directly determines which questions you can answer about the network.
Question 2 Multiple Choice
In the formal definition of a simple graph G = (V, E), edges are unordered pairs of *distinct* vertices. Why does 'distinct' appear in the definition?
ATo prevent the graph from containing any cycles
BTo ensure every vertex has a unique label
CTo prohibit loops — edges from a vertex to itself
DTo guarantee the graph remains connected
The word 'distinct' excludes the case {v, v} — a vertex connected to itself (a loop). Simple graphs have no loops by definition. This matters because loop-free graphs have different properties: for example, every vertex's degree counts only edges to other vertices, not self-connections. Multigraphs can relax this constraint. The definition is precise because every excluded structure is excluded for a reason.
Question 3 True / False
A theorem proven for simple graphs may not hold for multigraphs, because multigraphs permit structures that simple graphs explicitly exclude.
TTrue
FFalse
Answer: True
This is precisely why formal definitions matter in mathematics. Theorems are proven for all objects satisfying a given definition. A result about simple graphs — which have no loops and at most one edge between any pair — may rely on these restrictions in its proof. Multigraphs relax those constraints, so the proof no longer applies. For example, theorems about Eulerian circuits behave differently in multigraphs than in simple graphs. Knowing which definition you're working with determines which results you can use.
Question 4 True / False
In a directed graph, the edge (u, v) and the edge (v, u) represent the same connection viewed from opposite directions.
TTrue
FFalse
Answer: False
This is the most common misconception about directed graphs. Edges in a directed graph are ordered pairs, so (u, v) and (v, u) are entirely distinct edges — one goes from u to v, the other from v to u. A directed graph can contain both, one, or neither. This matters enormously: a web page can link to another without the other linking back; a road can be one-way; a dependency can be one-directional. Confusing directed edges with undirected ones would make it impossible to model asymmetric relationships.
Question 5 Short Answer
Why does choosing between a simple graph, directed graph, multigraph, or weighted graph matter before solving a graph problem?
Think about your answer, then reveal below.
Model answer: The definition specifies the model — it determines exactly which relationships can be represented and which questions can be asked. A shortest-path algorithm designed for weighted graphs has no meaning on an unweighted graph. A theorem about simple graphs may fail for multigraphs. A directed-graph reachability question ('Is there a path from u to v?') has a different answer than its undirected counterpart. Choosing the wrong model means your results don't apply to the actual problem you're solving.
Formal definitions in graph theory are not bureaucratic overhead — they are the specification of the object you're reasoning about. When you prove something about 'a graph,' you prove it about every graph satisfying the definition. Using the wrong definition means your conclusions may not transfer. In applied settings, the model choice shapes whether your answers are valid: modeling a one-way road network as an undirected graph would give incorrect routing results.