Connect a set of nodes with another set of the same size without intersections [duplicate]
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection
graph-theory
asked Nov 21 '18 at 19:42
svacxpython
82
marked as duplicate by Misha Lavrov, Ethan Bolker, user10354138, Lord Shark the Unknown, user26857 Nov 22 '18 at 9:51
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection
graph-theory
asked Nov 21 '18 at 19:42
svacxpython
82
marked as duplicate by Misha Lavrov, Ethan Bolker, user10354138, Lord Shark the Unknown, user26857 Nov 22 '18 at 9:51
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 '18 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 '18 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 '18 at 10:04
add a comment |
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection
graph-theory
asked Nov 21 '18 at 19:42
svacxpython
82
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
I am quite new to graphs (and could use some practice with math in general) and couldn't find a solution with zero intersections to this problem.
Assume you have two sets of 3 nodes (set H and set L) where each node (ex. h1, h2, h3) from one set should connect to every node on the other set (so l1, l2, l3). Is there any way you could arrange the connections so that there are no intersections?
Example of one edge intersection:
one edge intersection
This question already has an answer here:
3 Utilities | 3 Houses puzzle?
10 answers
graph-theory
graph-theory
asked Nov 21 '18 at 19:42
svacxpython
82
asked Nov 21 '18 at 19:42
svacxpython
82
asked Nov 21 '18 at 19:42
svacxpython
82
asked Nov 21 '18 at 19:42
svacxpython
82
asked Nov 21 '18 at 19:42
svacxpython
82
82
marked as duplicate by Misha Lavrov, Ethan Bolker, user10354138, Lord Shark the Unknown, user26857 Nov 22 '18 at 9:51
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Misha Lavrov, Ethan Bolker, user10354138, Lord Shark the Unknown, user26857 Nov 22 '18 at 9:51
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 '18 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 '18 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 '18 at 10:04
add a comment |
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 '18 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 '18 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 '18 at 10:04
1
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 '18 at 20:32
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 '18 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 '18 at 9:52
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 '18 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 '18 at 10:04
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 '18 at 10:04
add a comment |
1 Answer
1
active
oldest
votes
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 '18 at 23:20
mathnoob
1,799422
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 '18 at 23:20
mathnoob
1,799422
add a comment |
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 '18 at 23:20
mathnoob
1,799422
add a comment |
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 '18 at 23:20
mathnoob
1,799422
Here is a solution: A graph $G$ is planar then $|E(G)|leq 3|v(G)|-6$. If furthermore it is triangle free, then $|E(G)| leq 2|V(G)|-4$. For $K_{3,3}$, It doesn't contains triangle as it doesn't contain odd cycle. So apply the second formula we get: $9leq 2*6-4=8$ which is not possible! So it cannot be planar.
To show $|E(G)| leq 2|V(G)|-4$, we will use Euler's equation: $|V|-|E|+|F|$=2 for planar graph. Notice that if you count the total number of edges surrounding the faces, you count each edge twice. So $sum_{ain F(G)}{len(a)}=2|E(G)|$. Now since the graph has no triangle, each face is bounded by at least 4 edges. So $4|F(G)|leqsum_{ain F(G)}{len(a)}=2|E(G)|$. Solve for $|F|$ in Euler's equation and substitute into the previous inequality to get the desired inequality. Hope I got it right.
answered Nov 21 '18 at 23:20
mathnoob
1,799422
answered Nov 21 '18 at 23:20
mathnoob
1,799422
answered Nov 21 '18 at 23:20
mathnoob
1,799422
answered Nov 21 '18 at 23:20
mathnoob
1,799422
1,799422
add a comment |
add a comment |
1
(I don't mean to imply that you were wrong to ask this question - but this is the three utilities problem, which is very famous in graph theory, so it has been asked before, and there is no sense in reproducing the many good answers there.)
– Misha Lavrov
Nov 21 '18 at 20:32
@MishaLavrov thank you, I didnt know this was a known problem in graph theory
– svacxpython
Nov 22 '18 at 9:52
I think the problem is not solvable! Thank you both for the answers :)
– svacxpython
Nov 22 '18 at 10:04