Sandbox:DavidKohler/Alon try 1/Loopy
< Sandbox:DavidKohler/Alon try 1(Redirected from User:DavidKohler/Alon try 1/Loopy)
Definition
A connected graph G is loopy if it is not a tree. Equivalently, a graph is loopy if it has at least as many edges as vertices or if it contains an irreducible closed walk.
Furthermore, we say that the graph is 1-loopy if it connected and the removal of any edge leaves a graph each of whose connected components are loopy.
Properties
The following properties are consequences of theorem 3.9.
- A 1-loopy graph is not a cycle and has minimal degree 2.
- The associated graph of irreducible walks of a 1-loopy graph is strongly connected.