Mixing
Draw a simple graph where its vertices can be divided into 2 sets where every edge joins a vertex in one set...
$begingroup$
The question is:
Draw a simple graph with the following properties or explain why they do not exist.
The graph has 6 vertices and 8 edges and its vertices can be divided into two sets in such a way that every edge joins a vertex in one set to a vertex in the other.
I don't understand this question but I tried doing this. Since every vertex needs to join every other vertex (for example, in the scenario with two sets where 1 set has 1 vertex and the other has 5 vertices), does this mean that for this graph to exist, there has to be n(n-1)/2 edges?
graph-theory
asked Jan 13 at 15:59
llamaro25llamaro25
528
$endgroup$
|
show 1 more comment
$begingroup$
The question is:
Draw a simple graph with the following properties or explain why they do not exist.
The graph has 6 vertices and 8 edges and its vertices can be divided into two sets in such a way that every edge joins a vertex in one set to a vertex in the other.
I don't understand this question but I tried doing this. Since every vertex needs to join every other vertex (for example, in the scenario with two sets where 1 set has 1 vertex and the other has 5 vertices), does this mean that for this graph to exist, there has to be n(n-1)/2 edges?
graph-theory
asked Jan 13 at 15:59
llamaro25llamaro25
528
$endgroup$
$begingroup$
See answer here: en.wikipedia.org/wiki/Three_utilities_problem
$endgroup$
– David G. Stork
Jan 13 at 16:00
$begingroup$
Is a planar requirement missing?
$endgroup$
– Parcly Taxel
Jan 13 at 16:04
$begingroup$
@ParclyTaxel no, this is the entire question given
$endgroup$
– llamaro25
Jan 13 at 16:05
$begingroup$
@DavidG.Stork in the article, the cottages are not connected to each other. in order to answer my question, i should consider the scenario where the cottages and the utilities are connected to each other right?
$endgroup$
– llamaro25
Jan 13 at 16:06
$begingroup$
@meromero25: No. Re-read your question as stated: "in such a way that every edge joins a vertex in one set to a vertex in the other."
$endgroup$
– David G. Stork
Jan 13 at 16:07
|
show 1 more comment
$begingroup$
The question is:
Draw a simple graph with the following properties or explain why they do not exist.
The graph has 6 vertices and 8 edges and its vertices can be divided into two sets in such a way that every edge joins a vertex in one set to a vertex in the other.
I don't understand this question but I tried doing this. Since every vertex needs to join every other vertex (for example, in the scenario with two sets where 1 set has 1 vertex and the other has 5 vertices), does this mean that for this graph to exist, there has to be n(n-1)/2 edges?
graph-theory
asked Jan 13 at 15:59
llamaro25llamaro25
528
$endgroup$
The question is:
Draw a simple graph with the following properties or explain why they do not exist.
The graph has 6 vertices and 8 edges and its vertices can be divided into two sets in such a way that every edge joins a vertex in one set to a vertex in the other.
I don't understand this question but I tried doing this. Since every vertex needs to join every other vertex (for example, in the scenario with two sets where 1 set has 1 vertex and the other has 5 vertices), does this mean that for this graph to exist, there has to be n(n-1)/2 edges?
graph-theory
graph-theory
asked Jan 13 at 15:59
llamaro25llamaro25
528
asked Jan 13 at 15:59
llamaro25llamaro25
528
asked Jan 13 at 15:59
llamaro25llamaro25
528
asked Jan 13 at 15:59
llamaro25llamaro25
528
asked Jan 13 at 15:59
llamaro25llamaro25
528
528
$begingroup$
See answer here: en.wikipedia.org/wiki/Three_utilities_problem
$endgroup$
– David G. Stork
Jan 13 at 16:00
$begingroup$
Is a planar requirement missing?
$endgroup$
– Parcly Taxel
Jan 13 at 16:04
$begingroup$
@ParclyTaxel no, this is the entire question given
$endgroup$
– llamaro25
Jan 13 at 16:05
$begingroup$
@DavidG.Stork in the article, the cottages are not connected to each other. in order to answer my question, i should consider the scenario where the cottages and the utilities are connected to each other right?
$endgroup$
– llamaro25
Jan 13 at 16:06
$begingroup$
@meromero25: No. Re-read your question as stated: "in such a way that every edge joins a vertex in one set to a vertex in the other."
$endgroup$
– David G. Stork
Jan 13 at 16:07
|
show 1 more comment
$begingroup$
See answer here: en.wikipedia.org/wiki/Three_utilities_problem
$endgroup$
– David G. Stork
Jan 13 at 16:00
$begingroup$
Is a planar requirement missing?
$endgroup$
– Parcly Taxel
Jan 13 at 16:04
$begingroup$
@ParclyTaxel no, this is the entire question given
$endgroup$
– llamaro25
Jan 13 at 16:05
$begingroup$
@DavidG.Stork in the article, the cottages are not connected to each other. in order to answer my question, i should consider the scenario where the cottages and the utilities are connected to each other right?
$endgroup$
– llamaro25
Jan 13 at 16:06
$begingroup$
@meromero25: No. Re-read your question as stated: "in such a way that every edge joins a vertex in one set to a vertex in the other."
$endgroup$
– David G. Stork
Jan 13 at 16:07
$begingroup$
See answer here: en.wikipedia.org/wiki/Three_utilities_problem
$endgroup$
– David G. Stork
Jan 13 at 16:00
$begingroup$
See answer here: en.wikipedia.org/wiki/Three_utilities_problem
$endgroup$
– David G. Stork
Jan 13 at 16:00
$begingroup$
Is a planar requirement missing?
$endgroup$
– Parcly Taxel
Jan 13 at 16:04
$begingroup$
Is a planar requirement missing?
$endgroup$
– Parcly Taxel
Jan 13 at 16:04
$begingroup$
@ParclyTaxel no, this is the entire question given
$endgroup$
– llamaro25
Jan 13 at 16:05
$begingroup$
@ParclyTaxel no, this is the entire question given
$endgroup$
– llamaro25
Jan 13 at 16:05
$begingroup$
@DavidG.Stork in the article, the cottages are not connected to each other. in order to answer my question, i should consider the scenario where the cottages and the utilities are connected to each other right?
$endgroup$
– llamaro25
Jan 13 at 16:06
$begingroup$
@DavidG.Stork in the article, the cottages are not connected to each other. in order to answer my question, i should consider the scenario where the cottages and the utilities are connected to each other right?
$endgroup$
– llamaro25
Jan 13 at 16:06
$begingroup$
@meromero25: No. Re-read your question as stated: "in such a way that every edge joins a vertex in one set to a vertex in the other."
$endgroup$
– David G. Stork
Jan 13 at 16:07
$begingroup$
@meromero25: No. Re-read your question as stated: "in such a way that every edge joins a vertex in one set to a vertex in the other."
$endgroup$
– David G. Stork
Jan 13 at 16:07
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
Suppose our two vertex sets have $m$ and $n$ vertices respectively; if every edge links one vertex type to another, there can be at most $mn$ edges, when every pair of different-type vertices is connected by an edge.
In this question, $m+n=6$, so $(m,n)$ can be $(1,5),(2,4),(3,3)$, up to reversal of variables. These vertex sets allow for 5, 8 and 9 edges respectively. We reject $(m,n)=(1,5)$ as we need 8 edges. The other two choices lead to the two distinct solutions to the problem (the two vertex sets are marked with white and black circles):
answered Jan 13 at 16:20
Parcly TaxelParcly Taxel
41.8k1372101
$endgroup$
$begingroup$
thanks! but we should reject (3,3) as well right since it requires at least 9 edges to fulfil the statement "every edge joins a vertex in one set to a vertex in the other"
$endgroup$
– llamaro25
Jan 13 at 16:39
$begingroup$
also, for the (1,5) and (5,1) sets, can i draw it in such a way where the set with the 5 nodes have edges that join each other too?
$endgroup$
– llamaro25
Jan 13 at 16:40
$begingroup$
@meromero25 (1) we cannot reject $(3,3)$. There are merely more slots available for edges than we require edges. (2) no, since the edges between the set of five do not fit the problem statement.
$endgroup$
– Parcly Taxel
Jan 13 at 16:43
$begingroup$
oh, i see. thank you for the clarification!
$endgroup$
– llamaro25
Jan 13 at 16:44
add a comment |
$begingroup$
Without planarity requirement, the problem is only asking to have a bipartite graph : you need to be able to split the vertices in two "stable sets", i.e. two sets of vertices with no edges between vertices of the same set. As per wikipedia
a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$
For example :
The easiest exemple fitting the question would be $K_{2,4}$, the bipartite complete graph on 6 vertices, split in two groups. $U$ has size 4, $V$ has size $2$, and all elements of $U$ are linked to all elements of $V$
answered Jan 13 at 16:21
Thomas LesgourguesThomas Lesgourgues
778117
$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%2f3072146%2fdraw-a-simple-graph-where-its-vertices-can-be-divided-into-2-sets-where-every-ed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose our two vertex sets have $m$ and $n$ vertices respectively; if every edge links one vertex type to another, there can be at most $mn$ edges, when every pair of different-type vertices is connected by an edge.
In this question, $m+n=6$, so $(m,n)$ can be $(1,5),(2,4),(3,3)$, up to reversal of variables. These vertex sets allow for 5, 8 and 9 edges respectively. We reject $(m,n)=(1,5)$ as we need 8 edges. The other two choices lead to the two distinct solutions to the problem (the two vertex sets are marked with white and black circles):
answered Jan 13 at 16:20
Parcly TaxelParcly Taxel
41.8k1372101
$endgroup$
$begingroup$
thanks! but we should reject (3,3) as well right since it requires at least 9 edges to fulfil the statement "every edge joins a vertex in one set to a vertex in the other"
$endgroup$
– llamaro25
Jan 13 at 16:39
$begingroup$
also, for the (1,5) and (5,1) sets, can i draw it in such a way where the set with the 5 nodes have edges that join each other too?
$endgroup$
– llamaro25
Jan 13 at 16:40
$begingroup$
@meromero25 (1) we cannot reject $(3,3)$. There are merely more slots available for edges than we require edges. (2) no, since the edges between the set of five do not fit the problem statement.
$endgroup$
– Parcly Taxel
Jan 13 at 16:43
$begingroup$
oh, i see. thank you for the clarification!
$endgroup$
– llamaro25
Jan 13 at 16:44
add a comment |
$begingroup$
Suppose our two vertex sets have $m$ and $n$ vertices respectively; if every edge links one vertex type to another, there can be at most $mn$ edges, when every pair of different-type vertices is connected by an edge.
In this question, $m+n=6$, so $(m,n)$ can be $(1,5),(2,4),(3,3)$, up to reversal of variables. These vertex sets allow for 5, 8 and 9 edges respectively. We reject $(m,n)=(1,5)$ as we need 8 edges. The other two choices lead to the two distinct solutions to the problem (the two vertex sets are marked with white and black circles):
answered Jan 13 at 16:20
Parcly TaxelParcly Taxel
41.8k1372101
$endgroup$
$begingroup$
thanks! but we should reject (3,3) as well right since it requires at least 9 edges to fulfil the statement "every edge joins a vertex in one set to a vertex in the other"
$endgroup$
– llamaro25
Jan 13 at 16:39
$begingroup$
also, for the (1,5) and (5,1) sets, can i draw it in such a way where the set with the 5 nodes have edges that join each other too?
$endgroup$
– llamaro25
Jan 13 at 16:40
$begingroup$
@meromero25 (1) we cannot reject $(3,3)$. There are merely more slots available for edges than we require edges. (2) no, since the edges between the set of five do not fit the problem statement.
$endgroup$
– Parcly Taxel
Jan 13 at 16:43
$begingroup$
oh, i see. thank you for the clarification!
$endgroup$
– llamaro25
Jan 13 at 16:44
add a comment |
$begingroup$
Suppose our two vertex sets have $m$ and $n$ vertices respectively; if every edge links one vertex type to another, there can be at most $mn$ edges, when every pair of different-type vertices is connected by an edge.
In this question, $m+n=6$, so $(m,n)$ can be $(1,5),(2,4),(3,3)$, up to reversal of variables. These vertex sets allow for 5, 8 and 9 edges respectively. We reject $(m,n)=(1,5)$ as we need 8 edges. The other two choices lead to the two distinct solutions to the problem (the two vertex sets are marked with white and black circles):
answered Jan 13 at 16:20
Parcly TaxelParcly Taxel
41.8k1372101
$endgroup$
Suppose our two vertex sets have $m$ and $n$ vertices respectively; if every edge links one vertex type to another, there can be at most $mn$ edges, when every pair of different-type vertices is connected by an edge.
In this question, $m+n=6$, so $(m,n)$ can be $(1,5),(2,4),(3,3)$, up to reversal of variables. These vertex sets allow for 5, 8 and 9 edges respectively. We reject $(m,n)=(1,5)$ as we need 8 edges. The other two choices lead to the two distinct solutions to the problem (the two vertex sets are marked with white and black circles):
answered Jan 13 at 16:20
Parcly TaxelParcly Taxel
41.8k1372101
answered Jan 13 at 16:20
Parcly TaxelParcly Taxel
41.8k1372101
answered Jan 13 at 16:20
Parcly TaxelParcly Taxel
41.8k1372101
answered Jan 13 at 16:20
Parcly TaxelParcly Taxel
41.8k1372101
41.8k1372101
$begingroup$
thanks! but we should reject (3,3) as well right since it requires at least 9 edges to fulfil the statement "every edge joins a vertex in one set to a vertex in the other"
$endgroup$
– llamaro25
Jan 13 at 16:39
$begingroup$
also, for the (1,5) and (5,1) sets, can i draw it in such a way where the set with the 5 nodes have edges that join each other too?
$endgroup$
– llamaro25
Jan 13 at 16:40
$begingroup$
@meromero25 (1) we cannot reject $(3,3)$. There are merely more slots available for edges than we require edges. (2) no, since the edges between the set of five do not fit the problem statement.
$endgroup$
– Parcly Taxel
Jan 13 at 16:43
$begingroup$
oh, i see. thank you for the clarification!
$endgroup$
– llamaro25
Jan 13 at 16:44
add a comment |
$begingroup$
thanks! but we should reject (3,3) as well right since it requires at least 9 edges to fulfil the statement "every edge joins a vertex in one set to a vertex in the other"
$endgroup$
– llamaro25
Jan 13 at 16:39
$begingroup$
also, for the (1,5) and (5,1) sets, can i draw it in such a way where the set with the 5 nodes have edges that join each other too?
$endgroup$
– llamaro25
Jan 13 at 16:40
$begingroup$
@meromero25 (1) we cannot reject $(3,3)$. There are merely more slots available for edges than we require edges. (2) no, since the edges between the set of five do not fit the problem statement.
$endgroup$
– Parcly Taxel
Jan 13 at 16:43
$begingroup$
oh, i see. thank you for the clarification!
$endgroup$
– llamaro25
Jan 13 at 16:44
$begingroup$
thanks! but we should reject (3,3) as well right since it requires at least 9 edges to fulfil the statement "every edge joins a vertex in one set to a vertex in the other"
$endgroup$
– llamaro25
Jan 13 at 16:39
$begingroup$
thanks! but we should reject (3,3) as well right since it requires at least 9 edges to fulfil the statement "every edge joins a vertex in one set to a vertex in the other"
$endgroup$
– llamaro25
Jan 13 at 16:39
$begingroup$
also, for the (1,5) and (5,1) sets, can i draw it in such a way where the set with the 5 nodes have edges that join each other too?
$endgroup$
– llamaro25
Jan 13 at 16:40
$begingroup$
also, for the (1,5) and (5,1) sets, can i draw it in such a way where the set with the 5 nodes have edges that join each other too?
$endgroup$
– llamaro25
Jan 13 at 16:40
$begingroup$
@meromero25 (1) we cannot reject $(3,3)$. There are merely more slots available for edges than we require edges. (2) no, since the edges between the set of five do not fit the problem statement.
$endgroup$
– Parcly Taxel
Jan 13 at 16:43
$begingroup$
@meromero25 (1) we cannot reject $(3,3)$. There are merely more slots available for edges than we require edges. (2) no, since the edges between the set of five do not fit the problem statement.
$endgroup$
– Parcly Taxel
Jan 13 at 16:43
$begingroup$
oh, i see. thank you for the clarification!
$endgroup$
– llamaro25
Jan 13 at 16:44
$begingroup$
oh, i see. thank you for the clarification!
$endgroup$
– llamaro25
Jan 13 at 16:44
add a comment |
$begingroup$
Without planarity requirement, the problem is only asking to have a bipartite graph : you need to be able to split the vertices in two "stable sets", i.e. two sets of vertices with no edges between vertices of the same set. As per wikipedia
a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$
For example :
The easiest exemple fitting the question would be $K_{2,4}$, the bipartite complete graph on 6 vertices, split in two groups. $U$ has size 4, $V$ has size $2$, and all elements of $U$ are linked to all elements of $V$
answered Jan 13 at 16:21
Thomas LesgourguesThomas Lesgourgues
778117
$endgroup$
add a comment |
$begingroup$
Without planarity requirement, the problem is only asking to have a bipartite graph : you need to be able to split the vertices in two "stable sets", i.e. two sets of vertices with no edges between vertices of the same set. As per wikipedia
a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$
For example :
The easiest exemple fitting the question would be $K_{2,4}$, the bipartite complete graph on 6 vertices, split in two groups. $U$ has size 4, $V$ has size $2$, and all elements of $U$ are linked to all elements of $V$
answered Jan 13 at 16:21
Thomas LesgourguesThomas Lesgourgues
778117
$endgroup$
add a comment |
$begingroup$
Without planarity requirement, the problem is only asking to have a bipartite graph : you need to be able to split the vertices in two "stable sets", i.e. two sets of vertices with no edges between vertices of the same set. As per wikipedia
a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$
For example :
The easiest exemple fitting the question would be $K_{2,4}$, the bipartite complete graph on 6 vertices, split in two groups. $U$ has size 4, $V$ has size $2$, and all elements of $U$ are linked to all elements of $V$
answered Jan 13 at 16:21
Thomas LesgourguesThomas Lesgourgues
778117
$endgroup$
Without planarity requirement, the problem is only asking to have a bipartite graph : you need to be able to split the vertices in two "stable sets", i.e. two sets of vertices with no edges between vertices of the same set. As per wikipedia
a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$
For example :
The easiest exemple fitting the question would be $K_{2,4}$, the bipartite complete graph on 6 vertices, split in two groups. $U$ has size 4, $V$ has size $2$, and all elements of $U$ are linked to all elements of $V$
answered Jan 13 at 16:21
Thomas LesgourguesThomas Lesgourgues
778117
answered Jan 13 at 16:21
Thomas LesgourguesThomas Lesgourgues
778117
answered Jan 13 at 16:21
Thomas LesgourguesThomas Lesgourgues
778117
answered Jan 13 at 16:21
Thomas LesgourguesThomas Lesgourgues
778117
778117
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%2f3072146%2fdraw-a-simple-graph-where-its-vertices-can-be-divided-into-2-sets-where-every-ed%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$
See answer here: en.wikipedia.org/wiki/Three_utilities_problem
$endgroup$
– David G. Stork
Jan 13 at 16:00
$begingroup$
Is a planar requirement missing?
$endgroup$
– Parcly Taxel
Jan 13 at 16:04
$begingroup$
@ParclyTaxel no, this is the entire question given
$endgroup$
– llamaro25
Jan 13 at 16:05
$begingroup$
@DavidG.Stork in the article, the cottages are not connected to each other. in order to answer my question, i should consider the scenario where the cottages and the utilities are connected to each other right?
$endgroup$
– llamaro25
Jan 13 at 16:06
$begingroup$
@meromero25: No. Re-read your question as stated: "in such a way that every edge joins a vertex in one set to a vertex in the other."
$endgroup$
– David G. Stork
Jan 13 at 16:07