Fixed‐edge theorem for graphs with loops

Abstract

Abstract Let G be an undirected graph without multiple edges and with a loop at every vertex—the set of edges of G corresponds to a reflexive and symmetric binary relation on its set of vertices. Then every edge‐preserving map of the set of vertices of G to itself fixes an edge [{ f ( a ), f ( b )} = { a, b } for some edge ( a, b ) of G ] if and only if (i) G is connected , (ii) G contains no cycles, and (iii) G contains no infinte paths. The proof is conerned with those subgraphs H of a graph G for which there is an edge‐preserving map f of the set of vertices of G onto the set of vertices of H and satisfying f ( a ) = a for each vertex a of H .