A note on classes of subgraphs of locally finite graphs

We investigate the question how 'small' a graph can be, if it contains all members of a given class of locally finite graphs as subgraphs or induced subgraphs. More precisely, we give necessary and sufficient conditions for the existence of a connected, locally finite graph H containing all elements of a graph class G. These conditions imply that such a graph H exists for the class Gd consisting of all graphs with maximum degree < d which raises the question whether in this case H can be chosen to have bounded maximum degree. We show that this is not the case, thereby answering a question recently posed by Huynh et al.(c) 2023 Elsevier Inc. All rights reserved.