login
Hints
(Greetings from The On-Line Encyclopedia of Bongard Problems!)
Search: concept:graph
Displaying 1-10 of 14 results found. ( next )     page 1 2
     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

BP576 Vertices may be partitioned into two sets such that no two vertices in the same set are connected versus not so.
(edit; present; nest [left/right]; search; history)
COMMENTS

Left examples are called "bipartite graphs."

CROSSREFS

Adjacent-numbered pages:
BP571 BP572 BP573 BP574 BP575  *  BP577 BP578 BP579 BP580 BP581

KEYWORD

precise, allsorted, notso, math, traditional, preciseworld

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

WORLD

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

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

BP1099 Considering only the ways they are connected, anything that can be said about a given node can be said about every other node vs. not so.
(edit; present; nest [left/right]; search; history)
REFERENCE

https://en.wikipedia.org/wiki/Vertex-transitive_graph

CROSSREFS

Adjacent-numbered pages:
BP1094 BP1095 BP1096 BP1097 BP1098  *  BP1100 BP1101 BP1102 BP1103 BP1104

KEYWORD

precise, allsorted, notso, math, preciseworld

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

WORLD

graph [smaller | same | bigger]
zoom in left

AUTHOR

Leo Crabbe

( next )     page 1 2

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