While studying discrete maths I was having difficult to understand the following definition:

Here is a definition about connected graphs from the book Ralph Grimaldi - Discrete and Combinatorial Mathematics - 5ed.

(from page 517)

What I can't understand is the second property/definition, the one that says, when you have a directed graph, then if the associated undirected graph is connected, that implies that the directed graph will be connected too.

I could easily draw an example when this doesn't occurs: enter image description here

(2) is the undirected associated graph and IT'S CONNECTED.

But, I don't agree about that, I don't see how (1) can be connected too, because you don't have a path from d to a for example.

up vote 3 down vote accepted

I'll answer my own question because I find out where my thinking was wrong and also I found an alternative definition.

The following article explain the same as Grimaldi does, but calls it "weak connected" instead of just "connected", also defines the property of "connected" regarding directed graphs and not only regarding undirected graphs, so you understand better the concept. And what is better, the explanation uses a similar example like the one I draw in the question.

Here is the article:

http://www.brpreiss.com/books/opus4/html/page562.html

And what answer the question is that, in fact if you have a connected directed graph you don't necessary need to have a path between any two distinct vertices, that requirement is only if the graph is undirected.

I hope this 'auto-answer question' will help someone studying this same concept.

  • It just did brother! Thank you!! – user007 Jul 16 '15 at 21:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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