A network engineer needs to identify single edges whose failure would split a computer network into two disconnected parts. Which graph concept describes these edges?
AArticulation points, because vertices represent the servers that route traffic
BBridges, because these are edges whose removal increases the number of connected components
CComplete subgraphs, because they indicate fully redundant regions of the network
DIsolated vertices, because they are already disconnected from the network
A bridge is precisely an edge whose removal disconnects the graph — it is the single-edge analogue of an articulation point (a vertex whose removal increases components). In a network reliability context, bridges represent critical links with no redundancy. Option A is wrong because articulation points are vertices, not edges, and the question asks about individual connections. Identifying bridges and articulation points together gives a complete picture of single points of failure.
Question 2 Multiple Choice
A connected graph has 8 vertices. What is the minimum number of edges it can have while remaining connected?
A4 edges (n/2)
B7 edges (n−1), forming a spanning tree with no cycles
C8 edges (one per vertex)
D16 edges (2n, ensuring each vertex has degree 2)
A connected graph on n vertices requires at least n−1 edges. With exactly n−1 edges and no cycles, the graph is a tree — the minimally connected structure. With 8 vertices, that's 7 edges. Fewer than n−1 edges cannot connect all n vertices. Note that adding any edge to a tree creates exactly one cycle; removing any edge from a tree disconnects it. This minimal connectivity is why trees are foundational structures in graph theory and algorithm design.
Question 3 True / False
A complete graph (where nearly every pair of vertices is directly connected by an edge) is the same thing as a connected graph.
TTrue
FFalse
Answer: False
Connected means there exists a path between any two vertices — not that a direct edge exists. A tree is connected but far from complete: it has only n−1 edges while a complete graph on n vertices has n(n−1)/2 edges. A path graph (vertices in a line) is connected but has no vertex with more than 2 neighbors. Complete graphs are connected, but connectedness is a much weaker property. Confusing the two leads to overestimating the number of edges needed to maintain connectivity.
Question 4 True / False
In a connected graph, removing a bridge edge always increases the number of connected components, while removing a non-bridge edge never changes the number of components.
TTrue
FFalse
Answer: True
This is precisely the definition of a bridge: an edge is a bridge if and only if its removal increases the component count. Non-bridge edges are part of at least one cycle, so removing them leaves an alternative path between the previously connected vertices — the graph remains connected. This asymmetry is what makes bridge detection important: bridges are the fragile connections with no backup, while non-bridge edges have redundancy through cycles.
Question 5 Short Answer
Explain why a tree is called 'minimally connected,' and describe what happens to connectivity when you add one edge to a tree versus remove one edge from a tree.
Think about your answer, then reveal below.
Model answer: A tree is minimally connected because it has exactly the fewest edges (n−1) needed to connect n vertices, and every edge is a bridge — removing any single edge disconnects the tree into two components. Adding one edge to a tree creates exactly one cycle (and introduces a non-bridge edge, since the new cycle provides an alternative path). Removing any edge disconnects the tree. 'Minimal' means both that no edge is redundant and that no edge can be removed without loss of connectivity.
This minimal structure makes trees computationally valuable: spanning trees of a graph preserve connectivity while minimizing edges, useful for network design (minimizing cable length) and efficient traversal algorithms. The tension between connectivity and cycle-freedom is central to spanning tree algorithms like Kruskal's and Prim's.