Mixing
Coloring of two connected subgraphs
up vote
0
down vote
favorite
I have a graph made from two subgraphs: complete bi-parted $K_{4,4}$ and two triangles graph 
. These two subgraphs are connected by two edges. My task is to prove the number of proper 3-colorings for this graph. I can prove 3-colorings for $K_{4,4}$ and for two triangles, jet I cannot prove once they are connected together. Is there a way to make a "formal" proof for something like this?
Edit:
I was trying to prove it by multiplying the number of proper colorings and then dividing it be the number of incorrect combinations. There are 36 combinations for connection, but 18 are incorrect, so I divided the result of multiplication it by 2. The number is correct, jet it's not a correct proof.
graph-theory coloring
edited 17 hours ago
saulspatz
12.8k21327
asked 23 hours ago
onk
12
New contributor
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 1 more comment
up vote
0
down vote
favorite
I have a graph made from two subgraphs: complete bi-parted $K_{4,4}$ and two triangles graph . These two subgraphs are connected by two edges. My task is to prove the number of proper 3-colorings for this graph. I can prove 3-colorings for $K_{4,4}$ and for two triangles, jet I cannot prove once they are connected together. Is there a way to make a "formal" proof for something like this?
Edit:
I was trying to prove it by multiplying the number of proper colorings and then dividing it be the number of incorrect combinations. There are 36 combinations for connection, but 18 are incorrect, so I divided the result of multiplication it by 2. The number is correct, jet it's not a correct proof.
graph-theory coloring
edited 17 hours ago
saulspatz
12.8k21327
asked 23 hours ago
onk
12
New contributor
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
The diagram doesn't show the edges, at least not on my computer. I'm not sure it's possible to answer the question without this information. You say that the two subgraphs are joined by two edges, but you don't tell us anything about these two edges.
– saulspatz
23 hours ago
My bad, I updated the image, so it does not have a transparent background.
– onk
18 hours ago
What are you saying the correct answer is? I get $96$ three-colorings for $K_{4,4}$ and $6$ ways to extend each coloring to the triangle graph, so $576$ colorings in all.
– saulspatz
17 hours ago
There are $90$ 3-colorings for $K_{4,4}$ (coloring where both sides have just one color were counted multiple times) and 12 for the second graph. Once connected there are 540 proper 3-colorings (90*12/2).
– onk
17 hours ago
Yes, you're right. I double-counted. So $540$ is correct. Now I'm not sure what your question is. Are you saying you don't know how to independently justify the statement that half of the combined colorings are valid?
– saulspatz
14 hours ago
|
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have a graph made from two subgraphs: complete bi-parted $K_{4,4}$ and two triangles graph . These two subgraphs are connected by two edges. My task is to prove the number of proper 3-colorings for this graph. I can prove 3-colorings for $K_{4,4}$ and for two triangles, jet I cannot prove once they are connected together. Is there a way to make a "formal" proof for something like this?
Edit:
I was trying to prove it by multiplying the number of proper colorings and then dividing it be the number of incorrect combinations. There are 36 combinations for connection, but 18 are incorrect, so I divided the result of multiplication it by 2. The number is correct, jet it's not a correct proof.
graph-theory coloring
edited 17 hours ago
saulspatz
12.8k21327
asked 23 hours ago
onk
12
New contributor
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I have a graph made from two subgraphs: complete bi-parted $K_{4,4}$ and two triangles graph . These two subgraphs are connected by two edges. My task is to prove the number of proper 3-colorings for this graph. I can prove 3-colorings for $K_{4,4}$ and for two triangles, jet I cannot prove once they are connected together. Is there a way to make a "formal" proof for something like this?
Edit:
I was trying to prove it by multiplying the number of proper colorings and then dividing it be the number of incorrect combinations. There are 36 combinations for connection, but 18 are incorrect, so I divided the result of multiplication it by 2. The number is correct, jet it's not a correct proof.
graph-theory coloring
graph-theory coloring
edited 17 hours ago
saulspatz
12.8k21327
asked 23 hours ago
onk
12
New contributor
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 17 hours ago
saulspatz
12.8k21327
asked 23 hours ago
onk
12
New contributor
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 17 hours ago
saulspatz
12.8k21327
edited 17 hours ago
saulspatz
12.8k21327
edited 17 hours ago
saulspatz
12.8k21327
12.8k21327
asked 23 hours ago
onk
12
New contributor
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 23 hours ago
onk
12
asked 23 hours ago
onk
12
12
New contributor
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
onk is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
The diagram doesn't show the edges, at least not on my computer. I'm not sure it's possible to answer the question without this information. You say that the two subgraphs are joined by two edges, but you don't tell us anything about these two edges.
– saulspatz
23 hours ago
My bad, I updated the image, so it does not have a transparent background.
– onk
18 hours ago
What are you saying the correct answer is? I get $96$ three-colorings for $K_{4,4}$ and $6$ ways to extend each coloring to the triangle graph, so $576$ colorings in all.
– saulspatz
17 hours ago
There are $90$ 3-colorings for $K_{4,4}$ (coloring where both sides have just one color were counted multiple times) and 12 for the second graph. Once connected there are 540 proper 3-colorings (90*12/2).
– onk
17 hours ago
Yes, you're right. I double-counted. So $540$ is correct. Now I'm not sure what your question is. Are you saying you don't know how to independently justify the statement that half of the combined colorings are valid?
– saulspatz
14 hours ago
|
show 1 more comment
1
The diagram doesn't show the edges, at least not on my computer. I'm not sure it's possible to answer the question without this information. You say that the two subgraphs are joined by two edges, but you don't tell us anything about these two edges.
– saulspatz
23 hours ago
My bad, I updated the image, so it does not have a transparent background.
– onk
18 hours ago
What are you saying the correct answer is? I get $96$ three-colorings for $K_{4,4}$ and $6$ ways to extend each coloring to the triangle graph, so $576$ colorings in all.
– saulspatz
17 hours ago
There are $90$ 3-colorings for $K_{4,4}$ (coloring where both sides have just one color were counted multiple times) and 12 for the second graph. Once connected there are 540 proper 3-colorings (90*12/2).
– onk
17 hours ago
Yes, you're right. I double-counted. So $540$ is correct. Now I'm not sure what your question is. Are you saying you don't know how to independently justify the statement that half of the combined colorings are valid?
– saulspatz
14 hours ago
1
1
The diagram doesn't show the edges, at least not on my computer. I'm not sure it's possible to answer the question without this information. You say that the two subgraphs are joined by two edges, but you don't tell us anything about these two edges.
– saulspatz
23 hours ago
The diagram doesn't show the edges, at least not on my computer. I'm not sure it's possible to answer the question without this information. You say that the two subgraphs are joined by two edges, but you don't tell us anything about these two edges.
– saulspatz
23 hours ago
My bad, I updated the image, so it does not have a transparent background.
– onk
18 hours ago
My bad, I updated the image, so it does not have a transparent background.
– onk
18 hours ago
What are you saying the correct answer is? I get $96$ three-colorings for $K_{4,4}$ and $6$ ways to extend each coloring to the triangle graph, so $576$ colorings in all.
– saulspatz
17 hours ago
What are you saying the correct answer is? I get $96$ three-colorings for $K_{4,4}$ and $6$ ways to extend each coloring to the triangle graph, so $576$ colorings in all.
– saulspatz
17 hours ago
There are $90$ 3-colorings for $K_{4,4}$ (coloring where both sides have just one color were counted multiple times) and 12 for the second graph. Once connected there are 540 proper 3-colorings (90*12/2).
– onk
17 hours ago
There are $90$ 3-colorings for $K_{4,4}$ (coloring where both sides have just one color were counted multiple times) and 12 for the second graph. Once connected there are 540 proper 3-colorings (90*12/2).
– onk
17 hours ago
Yes, you're right. I double-counted. So $540$ is correct. Now I'm not sure what your question is. Are you saying you don't know how to independently justify the statement that half of the combined colorings are valid?
– saulspatz
14 hours ago
Yes, you're right. I double-counted. So $540$ is correct. Now I'm not sure what your question is. Are you saying you don't know how to independently justify the statement that half of the combined colorings are valid?
– saulspatz
14 hours ago
|
show 1 more comment
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
onk is a new contributor. Be nice, and check out our Code of Conduct.
onk is a new contributor. Be nice, and check out our Code of Conduct.
onk is a new contributor. Be nice, and check out our Code of Conduct.
onk is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3004845%2fcoloring-of-two-connected-subgraphs%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
1
The diagram doesn't show the edges, at least not on my computer. I'm not sure it's possible to answer the question without this information. You say that the two subgraphs are joined by two edges, but you don't tell us anything about these two edges.
– saulspatz
23 hours ago
My bad, I updated the image, so it does not have a transparent background.
– onk
18 hours ago
What are you saying the correct answer is? I get $96$ three-colorings for $K_{4,4}$ and $6$ ways to extend each coloring to the triangle graph, so $576$ colorings in all.
– saulspatz
17 hours ago
There are $90$ 3-colorings for $K_{4,4}$ (coloring where both sides have just one color were counted multiple times) and 12 for the second graph. Once connected there are 540 proper 3-colorings (90*12/2).
– onk
17 hours ago
Yes, you're right. I double-counted. So $540$ is correct. Now I'm not sure what your question is. Are you saying you don't know how to independently justify the statement that half of the combined colorings are valid?
– saulspatz
14 hours ago