Extremal graphs definition

Question

I'm trying to understand extremal graph theory using Diestel's book. I have two problems in it's introduction. First the definition of extremality for graph $H$ and $n$ vertices is somewhat confusing. As the first point, I want to verify whether my understanding is right.

My understanding of $ex(n,H)$ is as follows:

given $n$ vertices, if you add $ex(n,H)$ number of edges among these vertices, then, no matter which vertices you connect with these edges, an $H$ subgraph appears inside this graph. And if you lose any one of these $ex(n,H)$ number of edges, the $H$ subgraph disappears.

This is different from being edge maximal in respect to not having an $H$ subgraph because the edge maximality could depend on the current arrangement of the edges in the graph.

Is this correct?

That description in the book is confusing enough (specially being a non-native speaker) but what adds to the confusion is the following figure (which is going to be my second problem):

My understanding of $P^3$ is that its a path of three vertices, which already appears in the graph in the right. But the book claims that this graph is edge maximal with $P^3 \nsubseteq G$. Am I confused what $P^3$ means?

Any help would be appreciated.

EDIT: the book I'm referring to is reinhard diestel's book on graph theory: 2

Answer 1

The usual definition of $ex(n,H)$ is:

• there exists a graph with $n$ vertices, $ex(n,H)$ edges, and without a copy of $H$, and
• every graph with $n$ vertices and $ex(n,H)+1$ edges contains a copy of $H$.

Any graph which satisfies the first bullet point is then called extremal (with respect to the property of containing $H$).