Can an undirected graph be disconnected?
$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!
graph-theory connectedness directed-graphs
edited Dec 4 '18 at 23:42
Scientifica
6,75141335
asked Dec 4 '18 at 23:23
DevAllanPerDevAllanPer
1336
$endgroup$
add a comment |
$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!
graph-theory connectedness directed-graphs
edited Dec 4 '18 at 23:42
Scientifica
6,75141335
asked Dec 4 '18 at 23:23
DevAllanPerDevAllanPer
1336
$endgroup$
$begingroup$
if they are made of separate pieces.
$endgroup$
– hbm
Dec 4 '18 at 23:30
5
$begingroup$
Here's an example of (the diagram of) a disconnected undirected graph: $$huge ○,,,, ○$$
$endgroup$
– Git Gud
Dec 4 '18 at 23:30
add a comment |
$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!
graph-theory connectedness directed-graphs
edited Dec 4 '18 at 23:42
Scientifica
6,75141335
asked Dec 4 '18 at 23:23
DevAllanPerDevAllanPer
1336
$endgroup$
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!
graph-theory connectedness directed-graphs
graph-theory connectedness directed-graphs
edited Dec 4 '18 at 23:42
Scientifica
6,75141335
asked Dec 4 '18 at 23:23
DevAllanPerDevAllanPer
1336
edited Dec 4 '18 at 23:42
Scientifica
6,75141335
asked Dec 4 '18 at 23:23
DevAllanPerDevAllanPer
1336
edited Dec 4 '18 at 23:42
Scientifica
6,75141335
edited Dec 4 '18 at 23:42
Scientifica
6,75141335
edited Dec 4 '18 at 23:42
Scientifica
6,75141335
6,75141335
asked Dec 4 '18 at 23:23
DevAllanPerDevAllanPer
1336
asked Dec 4 '18 at 23:23
DevAllanPerDevAllanPer
1336
asked Dec 4 '18 at 23:23
DevAllanPerDevAllanPer
1336
1336
$begingroup$
if they are made of separate pieces.
$endgroup$
– hbm
Dec 4 '18 at 23:30
5
$begingroup$
Here's an example of (the diagram of) a disconnected undirected graph: $$huge ○,,,, ○$$
$endgroup$
– Git Gud
Dec 4 '18 at 23:30
add a comment |
$begingroup$
if they are made of separate pieces.
$endgroup$
– hbm
Dec 4 '18 at 23:30
5
$begingroup$
Here's an example of (the diagram of) a disconnected undirected graph: $$huge ○,,,, ○$$
$endgroup$
– Git Gud
Dec 4 '18 at 23:30
$begingroup$
if they are made of separate pieces.
$endgroup$
– hbm
Dec 4 '18 at 23:30
$begingroup$
if they are made of separate pieces.
$endgroup$
– hbm
Dec 4 '18 at 23:30
5
5
$begingroup$
Here's an example of (the diagram of) a disconnected undirected graph: $$huge ○,,,, ○$$
$endgroup$
– Git Gud
Dec 4 '18 at 23:30
$begingroup$
Here's an example of (the diagram of) a disconnected undirected graph: $$huge ○,,,, ○$$
$endgroup$
– Git Gud
Dec 4 '18 at 23:30
add a comment |
4 Answers
4
active
oldest
votes
$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:
answered Dec 4 '18 at 23:32
nafhgoodnafhgood
1,805422
$endgroup$
add a comment |
$begingroup$
Yes. The simplest such graph is just two vertices (no edges).
answered Dec 4 '18 at 23:30
plattyplatty
3,370320
$endgroup$
add a comment |
$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.
answered Dec 4 '18 at 23:31
KarenKaren
896
$endgroup$
add a comment |
$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.
answered Dec 4 '18 at 23:32
Stuartg98Stuartg98
586
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3026333%2fcan-an-undirected-graph-be-disconnected%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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:
answered Dec 4 '18 at 23:32
nafhgoodnafhgood
1,805422
$endgroup$
add a comment |
$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:
answered Dec 4 '18 at 23:32
nafhgoodnafhgood
1,805422
$endgroup$
add a comment |
$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:
answered Dec 4 '18 at 23:32
nafhgoodnafhgood
1,805422
$endgroup$
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:
answered Dec 4 '18 at 23:32
nafhgoodnafhgood
1,805422
answered Dec 4 '18 at 23:32
nafhgoodnafhgood
1,805422
answered Dec 4 '18 at 23:32
nafhgoodnafhgood
1,805422
answered Dec 4 '18 at 23:32
nafhgoodnafhgood
1,805422
1,805422
add a comment |
add a comment |
$begingroup$
Yes. The simplest such graph is just two vertices (no edges).
answered Dec 4 '18 at 23:30
plattyplatty
3,370320
$endgroup$
add a comment |
$begingroup$
Yes. The simplest such graph is just two vertices (no edges).
answered Dec 4 '18 at 23:30
plattyplatty
3,370320
$endgroup$
add a comment |
$begingroup$
Yes. The simplest such graph is just two vertices (no edges).
answered Dec 4 '18 at 23:30
plattyplatty
3,370320
$endgroup$
Yes. The simplest such graph is just two vertices (no edges).
answered Dec 4 '18 at 23:30
plattyplatty
3,370320
answered Dec 4 '18 at 23:30
plattyplatty
3,370320
answered Dec 4 '18 at 23:30
plattyplatty
3,370320
answered Dec 4 '18 at 23:30
plattyplatty
3,370320
3,370320
add a comment |
add a comment |
$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.
answered Dec 4 '18 at 23:31
KarenKaren
896
$endgroup$
add a comment |
$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.
answered Dec 4 '18 at 23:31
KarenKaren
896
$endgroup$
add a comment |
$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.
answered Dec 4 '18 at 23:31
KarenKaren
896
$endgroup$
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.
answered Dec 4 '18 at 23:31
KarenKaren
896
answered Dec 4 '18 at 23:31
KarenKaren
896
answered Dec 4 '18 at 23:31
KarenKaren
896
answered Dec 4 '18 at 23:31
KarenKaren
896
896
add a comment |
add a comment |
$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.
answered Dec 4 '18 at 23:32
Stuartg98Stuartg98
586
$endgroup$
add a comment |
$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.
answered Dec 4 '18 at 23:32
Stuartg98Stuartg98
586
$endgroup$
add a comment |
$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.
answered Dec 4 '18 at 23:32
Stuartg98Stuartg98
586
$endgroup$
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.
answered Dec 4 '18 at 23:32
Stuartg98Stuartg98
586
answered Dec 4 '18 at 23:32
Stuartg98Stuartg98
586
answered Dec 4 '18 at 23:32
Stuartg98Stuartg98
586
answered Dec 4 '18 at 23:32
Stuartg98Stuartg98
586
586
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3026333%2fcan-an-undirected-graph-be-disconnected%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
if they are made of separate pieces.
$endgroup$
– hbm
Dec 4 '18 at 23:30
5
$begingroup$
Here's an example of (the diagram of) a disconnected undirected graph: $$huge ○,,,, ○$$
$endgroup$
– Git Gud
Dec 4 '18 at 23:30