0
$\begingroup$

It is correct to say that a connected graph is only when there exist some vertex that is connected to all other vertices?

I think this is correct, because a connected graph not all vertices are connected together, but at least no vertex is not connected? Isn't that the above definition is saying?

I know the standard definition but I want to know if this definition is also correct. Thanks

$\endgroup$
7
  • $\begingroup$ What do you mean by "vertex $u$ is 'connected' to vertex $v$"? Do you mean that there is a path from $u$ to $v$? Or do you mean that $u$ and $v$ are joined by an edge of the graph? $\endgroup$
    – bof
    Commented Apr 5, 2014 at 21:57
  • $\begingroup$ I mean that in all graphs there is some vertex that is connected to (all) other vertices. $\endgroup$ Commented Apr 5, 2014 at 22:00
  • $\begingroup$ My question was, what does "connected to" mean? $\endgroup$
    – bof
    Commented Apr 5, 2014 at 22:03
  • $\begingroup$ That there is an edge between two vertices. $\endgroup$ Commented Apr 5, 2014 at 22:04
  • $\begingroup$ That's what I was afraid you meant. In standard terminology, $u$ is joined (or adjacent) to $v$ if there is an edge $uv$; they are connected if there is a path (possibly containing many edges) from $u$ to $v$. Consider the connected graph with $5$ vertices $u,v,w,x,y$ and $4$ edges $uv,vw,wx,xy$. The vertex $u$ is joined only to $v$, but it's connected to all the other vertices; it's connected to $y$ by the path $u,uv,v,vw,w,wx,x,xy,y$. $\endgroup$
    – bof
    Commented Apr 5, 2014 at 22:11

1 Answer 1

1
$\begingroup$

That is correct. A graph is connected if and only if for all $x, y \in V(G)$, there exists a path from $x$ to $y$.

When talking about directed graphs, we have the concepts of weak connectivity vs. strong connectivity. In a weakly connected graph, we are guaranteed either a directed $x-y$ path or a directed $y-x$ path, but not necessarily both. A strongly connected path guarantees us both a directed $x-y$ path and a directed $y-x$ path.

$\endgroup$
6
  • $\begingroup$ Thank you. So the above definition it is correct? $\endgroup$ Commented Apr 5, 2014 at 21:56
  • $\begingroup$ It is correct, but the universal quantifier strengthens the definition and reduces ambiguity. $\endgroup$
    – ml0105
    Commented Apr 5, 2014 at 21:56
  • $\begingroup$ We haven't told about the strong connectivity so we suppose that the definition is describing the plain connectivity? $\endgroup$ Commented Apr 5, 2014 at 21:58
  • $\begingroup$ This is the definition I'd use. It's a more exacting and stronger definition than the one you gave, no offense: "A graph is connected if and only if for all $x,y \in V(G)$, there exists a path from x to y." $\endgroup$
    – ml0105
    Commented Apr 5, 2014 at 21:59
  • $\begingroup$ @ml0105 Can we also say a graph is connected if there exists a walk between any 2 vertices ? Why are we emphasising on path ? $\endgroup$
    – Number945
    Commented Jan 17, 2018 at 23:37

You must log in to answer this question.

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