An example of Forbidden subgraph problem

97 Views Asked by At

The forbidden subgraph problem is one of the central problems in extremal graph theory. Given a forbidden subgraph $G$, the maximal number of edges in an $n$-vertex graph which does not have a subgraph isomorphic to $G$ is denoted as $ex(n,G)$. An equivalent problem is how many edges in an $n$-vertex graph guarantee that it has a subgraph isomorphic to $G$?

Now, I need to calculate $ex(4, P^3)$ and justify it with a proof. Is there an example of a graph on 4 vertices that is extremal in the set of all graphs without a $P^3$?

My idea so far: since $n=4,$ we would have ${ 4 \choose 2} =6$ edges. A copy of the complete bipartite graph $K_{1,3}$ and/or a copy of $C^3$ are the two types of graphs having the maximal of three edges which will not include $P^3.$ I am not sure about it let alone justify with a proof.