Let $G$ be an arbitrary undirected simple graph.
Make a list of some properties, which, if true for a graph $G$, are true for any super-graph of $G$.
For example, if there exists $p \in \{n\in \mathbb{N}: n \geq 2\}$ such that $G$ contains a cycle of length $2^p$ then any $H$, super-graph of $G$, there exists $p \in \{n\in \mathbb{N}: n \geq 2\}$ such that $H$ contains a cycle of length $2^p$
The properties you list must be substantially different from each-other. For example do not start listing from $k = 3$ to $100$, that if there exists a cycle of length $k$ in G, then there exists a cycle of length $k$ in any super graph of $G$.
I have posted this question before, and the question was closed. One of the persons who voted to close the question wrote to me,
"Homework problems are generally not appropriate on any stackexchange site without showing that you have worked on them […] this is a clearly undergraduate-level problem [...]”
I believed that it was easier to answer my original question without knowing why I was asking it. However, I see now that I must justify my motivations. It is clear to me now that questions have no merit in their own right. I am sorry for my mistake. My motivations are described below:
LEMMA 1
Any graph on $n$ nodes and minimum degree greater than or equal to $\delta$ has at least $(\delta/2)*n$ edges.
For example, a graph of min degree $\geq$ 4 has at least 2*n edges;
a graph of min degree $\geq$ 6 has at least 3*n edges;
and so on…
DEFINITION OF $F$
For any natural number $n$, let $F(n) = 1 + \lfloor n/2\rfloor* \lceil n/2 \rceil$
For large $n$, $F(n)$ approaches $1/2$ of the maximum possible number of edges in a graph.
THEOREM 1
For any graph, $G$, if $G$ contains at least $F(|V(G)|)$ edges, then there exists graph $G^{\prime}$, sub-graph of $G$, such that $|V(G^{\prime})| \leq |V(G)| - 1$ and $G^{\prime}$ has at least $F(|V(G^{\prime})|)$ edges
Proof:
Let $G$ be a graph having at least $F(|V(G)|)$ edges. For example, if $G$ has 18 nodes, then $G$ has at least 82 edges.
Let $G^{\prime}$ be a graph induced from $G$ by arbitrarily removing zero or more edges from $G$ such that $G^{\prime}$ has exactly $F(|V(G)|)$ edges.
If $G^{\prime}$ contains a sub-graph containing at least $F(|V(G)|)$ edges, then so does graph $G$
Let $\delta = \lfloor|V(G^{\prime})|/2 + 1\rfloor$
Given that we have $F(|V(G)|)$ edges, by LEMMA 1, $min degree (G^{\prime}) \leq (delta – 1)$
Let $v$ be vertex of minimum degree in graph $G^{\prime}$
Let $G^{\prime\prime}$ be graph $G^{\prime}$ with vertex $v$ removed.
It follows that $F(|V(G^{\prime\prime})|) \leq F(|V(G)|) – \delta \leq |E(G^{\prime\prime})|$
Therefore, $G^{\prime\prime}$ is a sub-graph of $G$ containing fewer vertices than $G$ such that $G^{\prime\prime}$ contains at least $F(|V(G^{\prime\prime})|)$ edges.
$QED$
THEOREM 2
Let $P$ be a property on graphs such that for any graph $G$, $P(G)$ implies $P(H)$ for any $H$ supergraph of $G$
If there exists natural $n$ such that for every graph, $G$, having $n$ nodes and $F(n)$ edges, $G$ has property $P$, then it follows that $P(H)$ for every graph $H$ such that $H$ has at least $F(|V(H)|)$ edges, so long as $|V(H)| \geq n$.
Proof:
We proceed by induction. We induct on the number of vertices in the graph
Base case:
There exists natural $n$ such that for every graph, $G$, having $n$ nodes and $F(n)$ edges, $G$ has property $P$.
Let $H$ be a super-graph of $G$ such that $H$ has at least $F(n)$ edges and $V(H) = V(G)$. By the definition of property $P$, we have $P(H)$.
Thus, $P(J)$ for all graphs $J$ having $n$ nodes and at least $F(n)$ edges
The inductive step follows from theorem 1.
$QED$
I basically want to know what implications of theorem 2 are interesting.
For example, any graph on $4$ vertices and at least $F(4) = 5$ edges, contains a power cycle.Therefore, any graph having at least 4 vertices and at least $F(|V(G)|)$ edges contains a power cycle. A power cycle is a cycle of length $2^p$ for integer $p \geq 2$
Ignoring power cycles, what else might we say?
Connectivity, Hamiltonicity, non-planarity, the property of containing any given graph as a subgraph...
The properties that have the property you want are known as "increasing graph properties," at least in the random graphs literature. See, for instance, Introduction to Random Graphs by Frieze and Karonski.