Connected component

• A “connected component” can be thought of as a “subgraph” of an undirected Graph
  • any independent set of vertices in the graph which are connected to each other with edges but are not connected to any other vertices in the “supergraph” (containing graph) qualifies as a “component”
    • these two vertices can be connected through other vertices, provided none of those vertices connect to any other vertices outside of the component
    • a single vertex with no edges qualifies as a component
    • a graph that is fully internally connected qualifies as one single component: the entire graph

E.g. a representation of 3 connected components in a graph with 10 vertices, given that edges exist as follows:

• 1-6-9
• 2-3-4-5-7-8

Then, the connected components are:

{0} {1 6 9} {2 3 4 5 7 8}