login
Hints
(Greetings from The On-Line Encyclopedia of Bongard Problems!)
Search: subworld:connected_graph
Displaying 1-10 of 10 results found.     page 1
     Sort: id      Format: long      Filter: (all | no meta | meta)      Mode: (words | no words)
BP390 Each graph vertex is uniquely defined by its connections (the graph does not admit nontrivial automorphisms) vs. the graph admits nontrivial automorphisms.
(edit; present; nest [left/right]; search; history)
CROSSREFS

Adjacent-numbered pages:
BP385 BP386 BP387 BP388 BP389  *  BP391 BP392 BP393 BP394 BP395

KEYWORD

precise, allsorted, notso, traditional, preciseworld

CONCEPT graph (info | search),
self-reference (info | search),
topological_transformation (info | search),
imagined_shape (info | search),
imagined_entity (info | search)

WORLD

connected_graph [smaller | same | bigger]

AUTHOR

Jago Collins

BP391 There exists an edge such that removing it yields two disconnected graphs (i.e., the minimum number of edges whose removal results in two disconnected graphs is 1) vs. the minimum number of edges whose removal results in two disconnected graphs is 2.
(edit; present; nest [left/right]; search; history)
CROSSREFS

Adjacent-numbered pages:
BP386 BP387 BP388 BP389 BP390  *  BP392 BP393 BP394 BP395 BP396

KEYWORD

nice, precise, traditional, preciseworld

CONCEPT graph (info | search),
distinguishing_crossing_curves (info | search),
existence (info | search),
imagined_shape (info | search),
imagined_entity (info | search)

WORLD

connected_graph [smaller | same | bigger]

AUTHOR

Jago Collins

BP560 There exists a closed trail that hits each edge exactly once vs. not so.
(edit; present; nest [left/right]; search; history)
COMMENTS

Left examples are called "Eulerian graphs."


A connected graph is Eulerian if and only if each vertex is incident to an even number of edges.

CROSSREFS

Adjacent-numbered pages:
BP555 BP556 BP557 BP558 BP559  *  BP561 BP562 BP563 BP564 BP565

KEYWORD

precise, allsorted, math, traditional, preciseworld

CONCEPT graph (info | search),
distinguishing_crossing_curves (info | search),
all (info | search),
even_odd (info | search),
existence (info | search)

WORLD

connected_graph [smaller | same | bigger]

AUTHOR

Aaron David Fairbanks

BP562 There exists a closed trail that hits each vertex exactly once vs. not so.
(edit; present; nest [left/right]; search; history)
COMMENTS

Left examples are called "Hamiltonian graphs."

CROSSREFS

Adjacent-numbered pages:
BP557 BP558 BP559 BP560 BP561  *  BP563 BP564 BP565 BP566 BP567

KEYWORD

math, traditional

CONCEPT graph (info | search),
distinguishing_crossing_curves (info | search)

WORLD

connected_graph [smaller | same | bigger]

AUTHOR

Aaron David Fairbanks

BP788 Graph contains a "loop" a.k.a. cycle (cyclic) versus graph is acyclic.
(edit; present; nest [left/right]; search; history)
CROSSREFS

Adjacent-numbered pages:
BP783 BP784 BP785 BP786 BP787  *  BP789 BP790 BP791 BP792 BP793

KEYWORD

nice, precise, allsorted, math, traditional, preciseworld

CONCEPT graph (info | search),
distinguishing_crossing_curves (info | search),
loop (info | search)

WORLD

connected_graph [smaller | same | bigger]

AUTHOR

Aaron David Fairbanks

BP854 Nothing vs. nothing.
(edit; present; nest [left/right]; search; history)
CROSSREFS

Adjacent-numbered pages:
BP849 BP850 BP851 BP852 BP853  *  BP855 BP856 BP857 BP858 BP859

KEYWORD

left-finite, right-finite, left-full, right-full, finished, experimental, funny

WORLD

nothing [same | bigger]
zoom in left (nothing) | zoom in right (nothing)

AUTHOR

Aaron David Fairbanks

BP905 Graph can be redrawn such that no edges intersect vs. not so.
(edit; present; nest [left/right]; search; history)
COMMENTS

A graph is a collection of vertices and edges. Vertices are the dots and edges are the lines that connect the dots. On the left, all edges can be redrawn (curved lines are allowed and moving vertices is allowed) such that no edges cross each other and each vertex is still connected to the same other vertices. These graphs are called planar.

CROSSREFS

Adjacent-numbered pages:
BP900 BP901 BP902 BP903 BP904  *  BP906 BP907 BP908 BP909 BP910

KEYWORD

nice, precise, allsorted, notso, math, left-null, preciseworld

CONCEPT graph (info | search),
topological_transformation (info | search)

WORLD

connected_graph [smaller | same | bigger]

AUTHOR

Molly C Klenzak

BP932 Every vertex is connected to every other vs. vertices are connected in a cycle (no other connections).
?
?
(edit; present; nest [left/right]; search; history)
COMMENTS

Complete graphs with zero, one, two, or three vertices would be ambiguously categorized (fit in overlap of both sides).


Left examples are called "fully connected graphs." Right examples are called "cycle graphs."

CROSSREFS

Adjacent-numbered pages:
BP927 BP928 BP929 BP930 BP931  *  BP933 BP934 BP935 BP936 BP937

KEYWORD

precise, left-narrow, right-narrow, both, preciseworld

CONCEPT graph (info | search),
distinguishing_crossing_curves (info | search),
all (info | search),
loop (info | search)

WORLD

connected_graph [smaller | same | bigger]

AUTHOR

Aaron David Fairbanks

BP1016 Rigid vs. not rigid.
(edit; present; nest [left/right]; search; history)
REFERENCE

Henneberg, L. (1911), Die graphische Statik der starren Systeme, Leipzig

Jackson, Bill. (2007). Notes on the Rigidity of Graphs.

Laman, Gerard. (1970), "On graphs and the rigidity of plane skeletal structures", J. Engineering Mathematics, 4 (4): 331–340.

Pollaczek‐Geiringer, Hilda (1927), "Über die Gliederung ebener Fachwerke", Zeitschrift für Angewandte Mathematik und Mechanik, 7 (1): 58–72.

CROSSREFS

Adjacent-numbered pages:
BP1011 BP1012 BP1013 BP1014 BP1015  *  BP1017 BP1018 BP1019 BP1020 BP1021

KEYWORD

nice, physics, help

CONCEPT rigidity (info | search),
graph (info | search),
imagined_motion (info | search)

WORLD

planar_connected_graph [smaller | same | bigger]
zoom in left (rigid_planar_connected_graph)

AUTHOR

Aaron David Fairbanks

BP1102 Nodes share the same edge connections as the vertices of a cube vs. not so.
(edit; present; nest [left/right]; search; history)
REFERENCE

https://mathworld.wolfram.com/CubicalGraph.html

CROSSREFS

Adjacent-numbered pages:
BP1097 BP1098 BP1099 BP1100 BP1101  *  BP1103 BP1104 BP1105 BP1106 BP1107

KEYWORD

precise, allsorted, arbitrary, help, preciseworld

CONCEPT graph (info | search),
cube (info | search),
distinguishing_crossing_curves (info | search),
topological_transformation (info | search)

WORLD

connected_graph [smaller | same | bigger]

AUTHOR

Leo Crabbe

    page 1

Welcome | Solve | Browse | Lookup | Recent | Links | Register | Contact
Contribute | Keywords | Concepts | Worlds | Ambiguities | Transformations | Invalid Problems | Style Guide | Goals | Glossary