Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can a single node graph be considered a (strongly) connected component?

I'm confused because I was reading about cut vertex which by definition is a vertex that if eliminated increases the number of connected components.

enter image description here

So if we were to remove vertex number 2, we would get 2 connected components?

Thanks!

share|improve this question

2 Answers 2

up vote 1 down vote accepted

A graph is connected if every pair of vertices in the graph can be connected by a path. By definition a single vertex is connected to itself by the trivial path. Hence, it is connected. If the graph is directed the same argument applies.

See also http://mathworld.wolfram.com/ConnectedGraph.html, specifically:

A graph which is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected. This definition means that the null graph and singleton graph are considered connected, while empty graphs on n>=2 nodes are disconnected.

share|improve this answer
    
This is a bad definition of connectivity: the correct definition should be that a connected graph is a graph with one connected component (connected components are the equivalence classes of the equivalence relation which is the transitive closure of the relation given by the edges). By this definition the empty graph is disconnected. See math.stackexchange.com/questions/50551/… . –  Qiaochu Yuan May 22 '12 at 17:54
    
@QiaochuYuan: hmm, yes, I haven't really thought about connectedness from a graph-theoretical (rather than a topological) point of view, but you are of course right. Nonetheless, I feel the post as it stands answers OP's question(s). –  M.B. May 22 '12 at 18:13

Reflexive property: For all a, a # a. Any vertex is strongly connected to itself, by definition. Source: https://www.ics.uci.edu/~eppstein/161/960220.html

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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