## Star Maps

by Benjamin L de Bivort

Answer: ðŸ“¦

The team received a jigsaw puzzle and a sheet printed on card stock. Assembled, the jigsaw looked like:

This mysterious image shows graphs (in the mathematical sense of nodes-connected by edges) and mysterious big red dots.

Each big red dot represents a type of graph, *e.g.,* INTEGRAL GRAPH.
This puzzle used graph-type names from MathWorld.

The handout showed these dots, along with blanks and stubby black lines. In the handout, the dots were in alphabetical order. Teams who had the insight that a dot was a graph type could use this to help determine which graph types the puzzle used. It wasn't immediately clear which handout-dot went with which jigsaw-dot.

The alphabetical list of graph types (*i.e.*, ordered as on the card stock sheet):

antiprismgraph

bicolorablegraph

bipartitegraph

bridgelessgraph

cayleygraph

circulantgraph

class1graph

class2graph

clawfreegraph

completebipartitegraph

completegraph

crossedprismgraph

crowngraph

cubicgraph

cyclegraph

disconnectedgraph

edgetransitivegraph

fangraph

forest

generalizedpetersengraph

gracefulgraph

gridgraph

haargraph

hamiltoniangraph

integralgraph

kpartitegraph

matchstickgraph

mobiusladder

nonhamiltoniangraph

nonplanargraph

pathgraph

perfectgraph

platonicgraph

polyhedralgraph

prismgraph

quarticgraph

rookgraph

selfcomplementarygraph

snark

squarefreegraph

stargraph

stronglyregulargraph

symmetricgraph

traceablegraph

tree

trianglefreegraph

unitdistancegraph

vertextransitivegraph

weaklyregulargraph

wheelgraph

Solvers had to combine information from the handout and the assembled jigsaw: they had to determine
which handout-dots corresponded to which jigsaw dots.
With the correct configuration, guided by the stubby black lines, a solver can connect big red dots.
Each connection passes through the drawing of a graph.
The passed-through graph will be in the types of the two connected big red dots;
*e.g.*, connections from the INTEGRAL GRAPH red dot pass through
integral graphs. Solvers can figure out which graph-type goes with a big red dot by looking at the little graph drawings and the dot's
blanks.

On the handout, each red dot has one numbered blank among its blanks.
By using the letters on those numbered blanks and ordering them, solvers get
the message ANSWER IS THE SUBGRAPH OF VERTICES WITH DEGREE TWO `K` PLUS ONE.
Interpreting this message, use the big-red-dot vertices, not the little-graph-image vertices.

Interpreting this message, use the big-red-dot vertices, not the little-graph-image vertices.
Identify the big-red-dot vertices that have an odd degree (2`k`+1),
and the subgraph they make up (all the edges between two odd-degreed big-red-dot vertices):

This is the solution: ðŸ“¦, the package emoji.

## The Graph Types

Here, the red dot graph types are listed by the number that appears in their blanks.â„– | Graph Type | |
---|---|---|

1 | integralgraph | a |

2 | platonicgraph | n |

3 | antiprismgraph | s |

4 | weaklyregulargraph | w |

5 | cayleygraph | e |

6 | completegraph | r |

7 | matchstickgraph | i |

8 | class2graph | s |

9 | forest | t |

10 | hamiltoniangraph | h |

11 | tree | e |

12 | stargraph | s |

13 | quarticgraph | u |

14 | bridgelessgraph | b |

15 | traceablegraph | g |

16 | vertextransitivegraph | r |

17 | haargraph | a |

18 | pathgraph | p |

19 | kpartitegraph | h |

20 | selfcomplementarygraph | o |

21 | fangraph | f |

22 | edgetransitivegraph | v |

23 | gracefulgraph | e |

24 | gridgraph | r |

25 | bipartitegraph | t |

26 | prismgraph | i |

27 | circulantgraph | c |

28 | wheelgraph | e |

29 | squarefreegraph | s |

30 | crowngraph | w |

31 | nonhamiltoniangraph | i |

32 | completebipartitegraph | t |

33 | rookgraph | h |

34 | mobiusladder | d |

35 | crossedprismgraph | e |

36 | bicolorablegraph | g |

37 | class1graph | r |

38 | trianglefreegraph | e |

39 | perfectgraph | e |

40 | disconnectedgraph | t |

41 | clawfreegraph | w |

42 | nonplanargraph | o |

43 | snark | k |

44 | cubicgraph | p |

45 | cyclegraph | l |

46 | stronglyregulargraph | u |

47 | unitdistancegraph | s |

48 | polyhedralgraph | o |

49 | generalizedpetersengraph | n |

50 | symmetricgraph | e |