I want to know how many cycles can be formed in the graph shown in the picture below. My professor told only two can be formed! I think three can be formed 1-2-3-4-5-6-1, 1-2-3-5-6-1,3-5-4-3. I am not sure, If I am correct, can someone tell me, how many cycles can be formed?
1 Answer
$\begingroup$This question is very vaguely worded. However, this might be a way to think about it.
We might consider induced subgraphs. For graphs $G$ and $H$, $H$ is an induced subgraph of $G$ if $V(H) \subseteq V(G)$ and $(x,y) \in E(H) \iff (x,y) \in E(G)$. A graph $G$ contains $H$ if $G$ has an induced subgraph isomorphic to $H$.
An induced cycle $C$ is an induced subgraph of $G$ isomorphic to a cycle. If $|C| > 3$, we call $H$ a hole or chordless cycle. If $|C|=3$, then $C$ is called a triangle.
We can rephrase the question by asking: How many induced cycles are contained in the given graph, let us call it $G$, as induced subgraphs?
The set $H_1=\{1,2,3,5,6\}$ induces a cycle in $G$, since $H_1 \subset V(G)$ and $E(H_1)$ preserves all edge relations of $E(G)$.
The set $H_2=\{3,4,5\}$ induces a cycle in $G$, since $H_2 \subset V(G)$ and $E(H_2)$ preserves all edge relations of $E(G)$.
Now, consider the set $H_3=\{1,2,3,4,5,6\}=V(G)$, then $H_3$ is the vertex set of a subgraph of $G$ and this subgraph is a cycle, so your thoughts are not wrong in general. However this subgraph $H_3$ is not induced if we drop the edge $(3,4)$. The edge $(3,4)$ is in $E(G)$, but it is not an edge in $H_3$.
$\endgroup$
