I am a bit confused about the notion of connected component of a graph. I understand what is a subgraph and what means for a graph to be connected. But the definition we got in class is this: "A connected component of a graph is a maximal connected subgraph.". My question is, if the subgraph is connected but it is not maximal connected, it isn't considered anymore a connected component? For example if we have 4 nodes and 4 edges forming a square, and we pick 4 nodes and only 3 of the edges, this is still connected, but it is not maximal connected. So this isn't anymore a connected component?

  • 1
    $\begingroup$ I don't understand what you're confused about. If it's not maximal, it's not a component. It's right there in the definition you quote. $\endgroup$ – David Richerby May 14 '16 at 14:27

Usually when defining components one considers "induced subgraphs", that is, all edges between the selected nodes are present in the subgraph. This contary to what you suggest, taking all nodes, but only a subset of the edges.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.