1
$\begingroup$

This may be a rather trivial question but I am still trying to get the hang of all the graph theory terms. Nonetheless, I haven't found a source that explicitly says that an undirected graph can only be connected so is it possible to have an undirected graph that is disconnected? And if so, may I have an example one?

Much thanks!

$\endgroup$
2
  • $\begingroup$ if they are made of separate pieces. $\endgroup$
    – hbm
    Commented Dec 4, 2018 at 23:30
  • 5
    $\begingroup$ Here's an example of (the diagram of) a disconnected undirected graph: $$\huge ○\,\,\,\, ○$$ $\endgroup$
    – Git Gud
    Commented Dec 4, 2018 at 23:30

4 Answers 4

7
$\begingroup$

Undirected just mean The edges does not have direction. connected means that there is a path from any vertex of the graph to any other vertex in the graph. so take any disconnected graph whose edges are not directed to give an example. following is one: enter image description here

$\endgroup$
4
$\begingroup$

Yes. The simplest such graph is just two vertices (no edges).

$\endgroup$
2
$\begingroup$

The definition of graph that I know is the following: A graph consists of two sets $(V,E)$ where $V$ is the set of vertices and $E$ is the set of edges.

The elements of $E$ are subsets (or multisets in the case of loops) of cardinality $2$ of $V$.

A graph is undirected if $\{x,y\}=\{y,x\}$ where $\{x,y\},\{y,x\}\in E$ and it is directed if $\{x,y\}\neq \{y,x\}$.

Therefore, by taking $V=\{a,b,c\}$ and $E=\{\{a,b\}\}$, you obtain a disconnected undirected graph.

$\endgroup$
2
$\begingroup$

I believe, since you can define a graph $G = (E,V)$ by its edge and vertex sets, it is perfectly ok to have a disconnected graph (i.e. a graph with no path between some vertices). In fact, taking $E$ to be empty still results in a graph.

$\endgroup$

You must log in to answer this question.

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