0
$\begingroup$

I understand that a graph is connected if there is a path between any two vertices.

However, I am unsure about the number of components of a graph. Is a single vertex considered a component? If yes, is it connected?

Image

In particular, what is the number of components in the below graph? Is it one or three?

$\endgroup$
2
  • 2
    $\begingroup$ The connected components of a graph partition the vertices into disjoint subsets. Therefore, it must be $3$. $\endgroup$ Commented Aug 7, 2023 at 8:50
  • $\begingroup$ "Components" in this context is short for "connected components". An isolated vertex is a connected component. $\endgroup$
    – Karl
    Commented Aug 7, 2023 at 12:13

1 Answer 1

2
$\begingroup$

By definition, for an undirected graph, i.e. a graph where edges have no direction associated with them a (connected) component is basically a set of vertices that are inter-reachable, or also a connected subgraph, and since isolated vertices can only "reach" themselves they are to be considered as connected components. Note that the word connected may be omitted but any component is still to be considered connected since this concept is intrinsic to the definition. Hence each "component" and "connected component" are typically intended as synonyms.

It follows that in your example there are $3$ connected components: $\left\{i\right\}$, $\left\{f\right\}$ and $\left\{e,g,h\right\}$.

In the case of directed graphs instead, we do not talk about connected components, but we distinguish between strongly and weakly connected components.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .