Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What is the difference between

connected

strongly-connected and

complete?

My understanding is:

connected: you can get to every vertex from every other vertex.

strongly connected: every vertex has an edge connecting it to every other vertex.

complete: same as strongly connected.

Is this correct?

share|improve this question

closed as no longer relevant by Vidit Nanda, Benjamin Steinberg, Henry Cohn, Daniel Moskovich, Misha Apr 18 '13 at 5:15

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

7  
I don't see a question about basic definitions that could be answered by consulting any glossary or undergraduate text on graph theory (e.g. see en.wikipedia.org/wiki/Glossary_of_graph_theory) as being appropriate here, but maybe that's just me. –  David Eppstein Dec 10 '09 at 23:04

2 Answers 2

up vote 10 down vote accepted
  • Connected is usually associated with undirected graphs (two way edges): there is a path between every two nodes.
  • Strongly connected is usually associated with directed graphs (one way edges): there is a route between every two nodes.
  • Complete graphs are undirected graphs where there is an edge between every pair of nodes.
share|improve this answer
    
I agree with Alex. Note that Strongly connected means "there is a route/path" instead of "there is an edge" between every two nodes. –  user2079 Nov 25 '09 at 20:24
    
Thank you! That's exactly what I was looking for. –  Goody Two Shoes Nov 25 '09 at 20:59
    
Alex, can you explain a bit more on the difference between a Connected Graph and a Complete Graph? It seems the only difference is that one uses path and the other uses edge. Aren't they the same? When you said for a Complete Graph, it's when: "are undirected graphs where there is an edge between every pair of nodes". Well, since it's an undirected graph then you can traverse both ways, hence why it's an "edge". But doesn't that mean the same as 'path'? I.e, there's a path between every two nodes that you can traverse between? So isn't that just the same as the definition of a Connected Graph –  user18992 Nov 3 '11 at 8:21
    
what is the difference between a path and a route? –  cacho Oct 29 '13 at 0:56

It is also important to remember the distinction between strongly connected and unilaterally connected. A directed graph is unilaterally connected if for any two vertices a and b, there is a directed path from a to b or from b to a but not necessarily both (although there could be). Strongly connected implies that both directed paths exist. This means that strongly connected graphs are a subset of unilaterally connected graphs.

And a directed graph is weakly connected if it's underlying graph is connected.

share|improve this answer

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