Menu
Let \(\mathcal{G}(n, m)\) denote the class of simple graphs on \(n\) vertices and \(m\) edges, and let \(G \in \mathcal{G}(n, m)\). For suitably restricted values of \(m\), \(G\) will necessarily contain certain prescribed subgraphs such as cycles of given lengths and complete graphs. For example, if \(m > \frac{1}{4}{n}^2\), then \(G\) contains cycles of all lengths up to \(\lfloor \frac{1}{2}(n+3) \rfloor\). Recently, we have established a number of results concerning the existence of certain subgraphs (cliques and cycles) in the subgraph of \(G\) induced by the vertices of \(G\) having some prescribed minimum degree. In this paper, we present some further results of this type. In particular, we prove that every \(G \in \mathcal{G}(n, m)\) contains a pair of adjacent vertices each having degree (in \(G\)) at least \(f(n, m)\) and determine the best possible value of \(f(n, m)\). For \(m > \frac{1}{4}{n}^{2}\), we find that \(G\) contains a triangle with a pair of vertices satisfying this same degree restriction. Some open problems are discussed.