# Elementary graph theory questions (periodicity and strongly connected components)

Just going through some graph theory concepts and I have two elementary questions which must be pretty trivial (but sometimes what seems trivial to me turns out to be wrong, so I'd be happy if someone could confirm that the following are indeed true):

(1) A periodic graph cannot self-loops - because self-loops are cycles of length 1.

Each graph $G$ can be split into strongly connected components and the 'rest of the world' $R$ (nodes in no connected component but with possible links to connected components).

(2) If $G$ is undirected, $R$ can only consist of isolated nodes (nodes with links to no other node).

• Could you expand on $(1)$? I'm not sure what it's asking. – none Dec 7 '15 at 4:49
• en.wikipedia.org/wiki/Aperiodic_graph – DrWatson Dec 7 '15 at 8:05
• Ah, the question looks like "A periodic graph" rather than "Aperiodic graph". For $1$ it seems that an aperiodic graph can have self-loops, since the definition asks for an integer $>1$ that divides the cycle lengths. For $2$, assume $R$ contains a non-isolated vertex. Then, that vertex forms a connected component of size $\geq 2$ in an undirected graph. – none Dec 7 '15 at 8:14
• @SanicHodgeheg A periodic graph is one that is not aperiodic, dude. Standard concept in graph theory. – mathse Dec 7 '15 at 8:30
• Your "disproof" of 2 seems to be wrong, too. You make a connected component out of $R$, but then $R$ does not satisfy its definition, which is: not to be a connected component. – mathse Dec 7 '15 at 8:37