This is my Bongard problem n. 21. We'll explore similar topics in several more problems. Try to write your solution (with a spoiler if you want). I'll give my solution under a spoiler in one or two days.
For more info about Bongard problems in general take a look at my first messages:
https://mathstodon.xyz/@leonardom/116110015131667314
https://mathstodon.xyz/@leonardom/116110093951382315
My solution to my BP20: on the left planar graphs, that is graphs that can be embedded on the plane (on the right graphs that can't).
Lot of interesting stuff in this Bongard Problem.
Detailed contents of each box:
1: a tree;
2: complete bipartite graph K(2, 3);
3: complete graph K(4);
4: net of the cube;
5: a random planar graph;
6: Goldner-Harary graph (It's maximal planar. All its faces are bounded by three edges.
See: https://en.wikipedia.org/wiki/Goldner%E2%80%93Harary_graph );
- - - -
7: complete graph K(5);
8: complete bipartite graph K(3, 3);
9: the famous Petersen graph (that contains a minor isomorphic to the K(3,3) graph, so it's non-planar. Its crossing number is 2. Toroidal).
See:
https://en.wikipedia.org/wiki/Petersen_graph
https://en.wikipedia.org/wiki/Toroidal_graph
10: the Grötzsch graph (it is the smallest triangle-free graph with chromatic number 4, it has Book thickness 3).
See (Wolfram Mathworld shows graphs in various ways, this is quite handy):
https://mathworld.wolfram.com/GroetzschGraph.html
https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph
11: complete bipartite graph K(3, 3) embedded on a torus, so it's toroidal (this is almost pixel art).
See:
http://www.cut-the-knot.org/do_you_know/3Utilities.shtml
12: (empty).
See also:
https://en.wikipedia.org/wiki/Planar_graph
https://en.wikipedia.org/wiki/Book_embedding
My Bongard problem n. 20. We're back to problems created by me. Quality may vary, etc. This topic is rich in ideas so I'll offer several more problems on it. Try to write your solution (with a spoiler if you want), and to spot any mistakes of mine. I'll give my solution to this problem under a spoiler in two days.
For more info about Bongard problems in general take a look at my first messages:
https://mathstodon.xyz/@leonardom/116110015131667314
https://mathstodon.xyz/@leonardom/116110093951382315
Sometimes you see a solution of a Bongard problem in few seconds. Sometimes you find a rule idea only after many minutes. And it may take more minutes to be reasonably sure your rule is true/false for all the given boxes. In several cases I have had to read things to find solutions or even to express the solution with correct formal words. In some cases I had to write down some Python/Rust code and process the box contents to be sure of the correctness of a solution of mine. So the amount of time needed by BPs varies a lot.
My solution to Aaron BP43: the left boxes contain representations of graphs with at least an odd cycle (cycle composed of an odd number of edges).
On the right there are trees, an incomplete bipartite graphs, and cycle graphs with an even length. As Grégoire Locqueville and Akshar Varma have noted, all of them can be 2-colored. This is an equivalent nicer solution.
"In a bipartite graph (bigraph), the graph's vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. In a bipartite graph, the length of every cycle is always even. This is because, in a cycle, each vertex must alternate between the two sets. If a cycle were to have an odd length, it would require a vertex to connect back to itself within the same set, which contradicts the definition of a bipartite graph."
The graph in box 1 is a F4:
https://en.wikipedia.org/wiki/Friendship_graph
See also:
https://en.wikipedia.org/wiki/Bipartite_graph
https://en.wikipedia.org/wiki/Graph_coloring
This is Aaron David Fairbanks Bongard problem n. 43. This is a little less basic/straightforward compared to the last problems, but I think it's still easy enough. Try to write your solution (with a spoiler if you want). I'll give my solution under a spoiler in some hours or tomorrow.
For more info about Bongard problems in general take a look at my first messages:
https://mathstodon.xyz/@leonardom/116110015131667314
https://mathstodon.xyz/@leonardom/116110093951382315
This was sufficiently related to the precedent problem, still about basic Graph properties.
Solution to Aaron BP41: the left boxes contain representations of graphs where all edges are part of one Eulerian cycle.
According to Wikipedia an Eulerian trail is a trail in a finite graph that visits every edge exactly once, allowing for revisiting vertices. An Eulerian cycle is an Eulerian trail that starts and ends on the same node. [... A] necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree.
This is Aaron David Fairbanks Bongard problem n. 41. Try to write your solution (with a spoiler if you want). I'll give my solution under a spoiler tomorrow (one more to go before going back to my problems).
For more info about Bongard problems in general take a look at my first messages:
https://mathstodon.xyz/@leonardom/116110015131667314
https://mathstodon.xyz/@leonardom/116110093951382315
On the same topics, this is Aaron David Fairbanks Bongard problem n.42. Try to write your solution (with a spoiler if you want). I'll give my solution under a spoiler in few hours.
For more info about Bongard problems in general take a look at my first messages:
https://mathstodon.xyz/@leonardom/116110015131667314
https://mathstodon.xyz/@leonardom/116110093951382315
My solution to Jago Collins problem n.391: the boxes on the left contain representations of graphs with at least one bridge (a bridge is an edge that once removed leads to an increase of the number of connected components of the graph).
See also:
https://en.wikipedia.org/wiki/Bridge_(graph_theory)
I'll offer few more problerms on such topics, that present so many significant ideas.
#bongardproblem #mathpuzzle #puzzle #visualmath
---------------------------------------
I'll offer few more Bongard problems on this topic created by other people, as an introduction. This is Jago Collins problem n.391. Try to write your solution (with a spoiler if you want). I'll give my solution under a spoiler in few hours. For the problems created by others I'll keep a faster pace.
For more info about Bongard problems in general take a look at my first messages:
https://mathstodon.xyz/@leonardom/116110015131667314
https://mathstodon.xyz/@leonardom/116110093951382315
leonardo m.
