Paths, components and bridges
Reachability is unchanged by moving vertices in the drawing. Include isolated vertices when counting components
- Path A simple path follows adjacent vertices without repeating a vertex
- Cycle A simple cycle returns to its start, with no other repeated vertex. In a simple graph it has at least three edges
- Components Each component is a maximal group linked by paths. Isolated vertices are one-vertex components
- Bridge Removing a bridge increases the number of components. A cycle edge is not a bridge because the rest of its cycle gives another route
Worked example
A graph has edges AB, BC, CA and CD. Identify its bridge and explain why the three triangle edges are not bridges
\[\begin{gathered}c(G)=1\\c(G-CD)=2\end{gathered}\]
- \(\displaystyle E=\{AB,BC,CA,CD\}\)A, B and C form a cycle, and D is joined only by CD
- \(\displaystyle c(G)=1,\quad c(G-CD)=2\)Deleting CD separates D; it is a bridge
- \(\displaystyle c(G-AB)=1\)After removing AB, A and B remain connected through C. The same alternate-route argument applies to BC and CA
Common mistakes
Positive degree is not connectedness
✕Every degree is positive, so the graph is connected✓Two separate cycles have positive degrees but are disconnected
Reachability between different components is still missingConfusing components with a bipartition
✕Two vertex classes mean two components✓Components are reachability groups; bipartition classes constrain edge endpoints
A connected bipartite graph may have one componentExcluding an isolated vertex from the count
✕Only vertices on edges count as components✓An isolated vertex is its own component
The vertex set includes vertices that have no incident edgeDifficulty levels
introRecognise connected or disconnected graphs using a valid reachability reason. Bridge calculation remains a later practice extension
Questions about this topic
Is one vertex with no edges connected?+
Yes. It has one component; the condition on every pair of distinct vertices has no failing pair
Why can deleting a cycle edge leave the graph connected?+
The rest of that cycle gives a route between the removed edge’s endpoints. Other connections do not need that edge uniquely
Does this lesson assess all walk classifications?+
No. It introduces paths and cycles needed for tree reasoning. Later work treats trails, circuits and Euler/Hamilton conditions
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 11, VCE Units 1 & 2, Specialist Mathematics, chapter 2: Graph theory
In this chapter
Count the vertices, edges and loops of a graphRepresent a network in a matrixIdentify the network a connection matrix describesDegrees, the degree sum, and even and odd vertices2B Graph families and structure: Graph types, subgraphs, connection models and method selectionConnected graphs and bridgesIdentify isomorphic graphsTrees and spanning treesGraph families and tree conditionsPlanar graphs and drawings in planar formFaces and Euler's formula2C Planarity and graph proofs: Graph types, subgraphs, connection models and method selectionClassify a route: walk, trail, path, circuit or cycleEulerian trails and circuits: existence and identificationHamiltonian paths and cycles