/sci/ - Science & Math » Thread #14082624

41KiB, 334x318, Johnsonsolidskeleton35.png

View Same Google iqdb SauceNAO

Graph theory

Anonymous Mon 10 Jan 13:59:03 2022 No.14082624 View Reply Original Report

Quoted By: >>14084508 >>14084810 >>14085684

Pic related is a 4-edge connected graph :
Every two vertices of G form the endpoints of 4 paths, no two of which share an edge with each other.

I would like to colour the edges of the graph in two colours (say, red and green) in such a way that for any pair of vertices, two paths are green and the two others are red.

I was told that it is not possible. Is there an easy way to prove it ?

Anonymous

Anonymous Mon 10 Jan 2022 21:07:59 No.14084452 Report

Quoted By:

bump

Anonymous

Anonymous Mon 10 Jan 2022 21:17:49 No.14084508 Report

Quoted By:

>>14082624
/sci/ has always been painfully deficient of ramsey chads. 2^18 is baby tier combinatorics so the easiest proof is to just do a sat; i'm sure you could even do it on your iphone architecture

Anonymous

View Same Google iqdb SauceNAO sad graph.png, 35KiB, 334x318

Anonymous Mon 10 Jan 2022 22:16:10 No.14084810 Report

Quoted By: >>14084854 >>14085262

>>14082624
I can't prove it but you might be able to.
Because every vertex has 4 edges and paths between any 2 vertices cannot share edges, every vertex needs exactly 2 green and 2 red edges. The only way for a vertex with 2 red edges to connect to any other vertex that has 2 red edges by going only along red edges is if those vertices are on a Hamiltonian cycle (a path that cycles through every vertex exactly once that doesn't go through the same edge more than once).
This means that for this graph to have the property you want, there must exist a pair of Hamiltonian cycles that do not share any edge. Now, I can't prove it but I'm almost certain that there are no such pair of cycles for this graph specifically.
Any time you make a red cycle that visits every vertex, the remaining edges will form 2 disconnected green cycles meaning that points chosen from separate green cycles will not satisfy the condition of having both 2 red and 2 green paths between them.

Anonymous

Anonymous Mon 10 Jan 2022 22:23:30 No.14084854 Report

Quoted By:

>>14084810
nice reformulation. cuts the sat down to proving W(2,2)=9 and you can probably do that on an abacus architecture

Anonymous

Anonymous Mon 10 Jan 2022 23:53:28 No.14085262 Report

Quoted By:

>>14084810
Yeah, i saw that too but unfortunately i still didn't know how to conclude.

I tried to assign colors to some edges arbitrarily, and to prove that no solution could have this assignement, but it did not work well. I mean, the proof would probably work but it takes much longer than what i was expecting.

Anonymous

Anonymous Tue 11 Jan 2022 02:13:28 No.14085684 Report

Quoted By:

>>14082624
Stop trying to do the most difficult way with a flat plane. Draw it as a 3d perspective and use your color scheme along with z axis to show what you want.

Anonymous

Anonymous Tue 11 Jan 2022 07:44:28 No.14086402 Report

Quoted By:

Bump

Anonymous

Anonymous Tue 11 Jan 2022 17:22:55 No.14087700 Report

Quoted By:

Maybe try something using the probabilistic method. I think it shouldn't be too hard. You should give it a try first but I'll maybe give it a think.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches