I am trying to write a proof about cycles and undirected graphs but I am confused by something.
If my graph has only 2 vertices and one edge connecting them, that is not a cycle, is it?
So I need at least 3 vertices with 2 connections from 2 vertices to one of the nodes and one between the other two to have the minimum possible cycle (a tringle) in a graph. Or am I approaching it wrong?
Yes the simplest possible cycle can be created with 3 nodes.
Having a graph with 2 nodes is not a cycle and it cannot be a cycle because it conflicts with the rule for a set of nodes to contain a cycle.If you have 3 nodes then it is possible to have a cycle if every node has at least 2 edges.
In order for you check for a cycle you must check the following rule:
If you look at all the neighbors of a node and there is one that is already visited and it is different from the previous one you visited then you have a cycle.
as the article says on Wikipedia: https://en.wikipedia.org/wiki/Cycle_graph
a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn. The number of vertices in Cn equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it
So, "If my graph has only 2 vertices and one edge connecting them, that is not a cycle, is it?" NO..
"So I need at least 3 vertices with 2 connections from 2 vertices to one of the nodes and one between the other two to have the minimum possible cycle (a tringle) in a graph":- that's right.
