{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e3bef1",
   "metadata": {},
   "source": [
    "# Finding a cycle\n",
    "\n",
    "**Theorem.** If every vertex of a finite graph $G$ has degree at least 2, then $G$ contains a cycle.\n",
    "\n",
    "**Proof.** Start anywhere and walk along edges, never going straight back along the edge you just used. Every vertex has a second neighbour, so the walk never gets stuck. There are finitely many vertices, so eventually the walk visits a vertex it has seen before. The part of the walk between the two visits is a cycle. $\\square$\n",
    "\n",
    "The proof is an algorithm. Your job is to turn it into a Sage function `cycle_or_none(G)`:\n",
    "\n",
    "- if $\\delta(G) \\geq 2$, return a cycle as a list of vertices;\n",
    "- if $\\delta(G) < 2$ and $G$ is a tree, print `\"You're a tree!\"` and return `None`;\n",
    "- otherwise, return `None`.\n",
    "\n",
    "The first sections are a reference for the Sage and Python you need. Run each cell with **Shift+Enter**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "102c77",
   "metadata": {},
   "source": [
    "## Graphs in Sage\n",
    "\n",
    "Sage has a library of named graphs under `graphs.`; type `graphs.` and press **Tab** to see them all. You can also build a graph from a list of edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d12c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = graphs.PathGraph(4)               # 0 - 1 - 2 - 3\n",
    "H = graphs.PetersenGraph()\n",
    "K = Graph([(0, 1), (1, 2), (2, 0), (2, 3)])  # a triangle with a pendant edge\n",
    "\n",
    "print(G.vertices())         # [0, 1, 2, 3]\n",
    "print(G.edges(labels=False))  # [(0, 1), (1, 2), (2, 3)]\n",
    "print(G.order(), G.size())  # number of vertices, number of edges: 4 3\n",
    "print(G.neighbors(1))       # the neighbours of vertex 1: [0, 2]\n",
    "print(G.has_edge(0, 1))     # True\n",
    "print(2 in G.neighbors(0))  # False, since 0 and 2 are not adjacent\n",
    "print(G.degree())           # degree of every vertex: [1, 2, 2, 1]\n",
    "print(min(G.degree()))      # minimum degree: 1\n",
    "print(G.is_connected())     # True\n",
    "K.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f19ab",
   "metadata": {},
   "source": [
    "## Lists in Python\n",
    "\n",
    "A list is an ordered sequence. Positions start at 0, and negative positions count from the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "285c27",
   "metadata": {},
   "outputs": [],
   "source": [
    "c = [1, 2, 3, 4, 5]\n",
    "print(c[2])         # the element at position 2, which is the third one: 3\n",
    "print(c[-1])        # the last element: 5\n",
    "print(6 in c)       # False\n",
    "c.append(6)         # add 6 to the end\n",
    "print(c)            # [1, 2, 3, 4, 5, 6]\n",
    "print(c.index(6))   # the first position where 6 appears: 5\n",
    "print(c[2:])        # the slice from position 2 to the end: [3, 4, 5, 6]\n",
    "print(c[2:4])       # positions 2 and 3, stopping before 4: [3, 4]\n",
    "# c.index(7) would raise an error, because 7 is not in c"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7960ce",
   "metadata": {},
   "source": [
    "## Two helpers\n",
    "\n",
    "These pick a vertex out of a list. Feel free to use them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e84509",
   "metadata": {},
   "outputs": [],
   "source": [
    "def elt_of(iterable):\n",
    "    # Return the first element of a list (or set, or anything you can loop over).\n",
    "    for u in iterable:\n",
    "        return u\n",
    "\n",
    "def elt_of_but_not(iterable, exclude):\n",
    "    # Return the first element that is not equal to `exclude`.\n",
    "    for u in iterable:\n",
    "        if u != exclude:\n",
    "            return u\n",
    "\n",
    "print(elt_of([4, 5, 6]))             # 4\n",
    "print(elt_of_but_not([4, 5, 6], 4))  # 5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "975a6a",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Fill in `cycle_or_none`. Keep the walk in a list `ls`, so `ls[-1]` is where you are now and `ls[-2]` is where you just came from."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9f9f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cycle_or_none(G):\n",
    "    # Take a graph. If min degree >= 2, return a cycle as a list of vertices.\n",
    "    # If G is a tree, print \"You're a tree!\" and return None. Otherwise return None.\n",
    "\n",
    "    # Step 1. If the minimum degree is less than 2, the walk might get stuck.\n",
    "    #         Print \"You're a tree!\" if G is a tree, then return None.\n",
    "    #         Useful: G.degree(), G.order(), G.size(), G.is_connected()\n",
    "\n",
    "    # Step 2. Start the walk: a list holding any vertex, then one of its neighbours.\n",
    "\n",
    "    # Step 3. Repeat: append a neighbour of the last vertex, other than the one\n",
    "    #         before it. As soon as the newest vertex already appeared earlier\n",
    "    #         in the list, return the part of the list that forms the cycle.\n",
    "    #         Useful: ls[-1], ls[-2], ls.index(v), ls[i:j]\n",
    "\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad7407",
   "metadata": {},
   "source": [
    "## Testing\n",
    "\n",
    "`is_cycle(G, C)` checks that `C` really is a cycle of `G`: at least 3 distinct vertices, each adjacent to the next, and the last adjacent to the first. Run the cell below once your function is done."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f1634",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_cycle(G, C):\n",
    "    return (C is not None and len(C) >= 3 and len(set(C)) == len(C)\n",
    "            and all(G.has_edge(C[i], C[(i + 1) % len(C)]) for i in range(len(C))))\n",
    "\n",
    "examples = [\n",
    "    (\"K4\",                   graphs.CompleteGraph(4),          \"cycle\"),\n",
    "    (\"Petersen\",             graphs.PetersenGraph(),           \"cycle\"),\n",
    "    (\"C7\",                   graphs.CycleGraph(7),             \"cycle\"),\n",
    "    (\"cube\",                 graphs.CubeGraph(3),              \"cycle\"),\n",
    "    (\"path\",                 graphs.PathGraph(5),              \"None\"),\n",
    "    (\"random tree\",          graphs.RandomTree(10),            \"None\"),\n",
    "    (\"triangle + pendant\",   Graph([(0, 1), (1, 2), (2, 0), (2, 3)]), \"None\"),\n",
    "    (\"triangle + isolated\",  graphs.CycleGraph(3) + Graph(1),  \"None\"),\n",
    "]\n",
    "\n",
    "for name, G, expected in examples:\n",
    "    C = cycle_or_none(G)\n",
    "    ok = is_cycle(G, C) if expected == \"cycle\" else C is None\n",
    "    print(f\"{name:22} expect {expected:6} got {str(C):28} {'ok' if ok else 'WRONG'}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.10",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.14.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}