Tilde Logo

/challenges

February 2025

For n2n \geq 2, define the graph GnG_n:
  • Vertices: Ordered pairs (x,y)(x, y) with 1x,yn1 \leq x, y \leq n and xyx \neq y.
  • Edges: (x1,y1)(x2,y2)(x_1, y_1) \sim (x_2, y_2) if x1+y1=x2+y2x_1 + y_1 = x_2 + y_2 or x1y1=x2y2x_1 - y_1 = x_2 - y_2.
Define L(Gn)L(G_n), the line graph of GnG_n:
  • Vertices: Edges of GnG_n.
  • Edges: Two vertices are adjacent if their corresponding edges share a vertex in GnG_n.
Find the number of induced subgraphs of L(Gn)L(G_n) where every vertex has degree 2.
Express this count as an explicit function of nn.

Original graph
Original graph of G4G_4
Line graph
Line graph of G4G_4

Answer

1-2 sentences explaining your reasoning