Some doubts on the definition of minimality of a graph. EDITED

Question

If a graph $G$ is minimal with property $P$, does that specifically mean:

1. Any proper subgraph of $G$ does not have that property $P$? Or,

2. Any graph with less number of vertices or less number of edges than $G$ does not have property $P$, the graph does not necessarily have to be a subgraph of $G$?

I am really confused about this concept and I couldn't find any proper definition of minimality.

EDITED

The reason I asked this question is because I found a proof where the author used option 2 as the definition of minimality.

Here is an example:

If there exists a minimal example $G$ of a non-planar graph with no Kuratowski subgraph, then it is 3-connected.

Proof:

$G$ is a minimal non-planar graph. Then $G$ is 2-connected. If $G$ is 3-connected then it has a minimal vertex cut $\{x,y\}$. Let the connected components of $G-x-y$ be $H_1,\ldots,H_k$. Then WLOG $G[H_1+x+y]+xy$ is non-planar. Moreover, $G[H_1+x+y]+xy$ has fewer elements than $G$, therefore by minimality of $G$ it contains a Kuratowski subgraph $K$. Continued below...

The author mentioned, since it has fewer elements and by minimality ... So I guess he used option 2 as the definition of minimality.

I continue the proof for reference:

Since $K$ cannot be a subgraph of $G$, $xy\in K$ and $xy\notin G$, and since $\{x,y\}$ is a minimal vertex cut, there is an edge from $x$ to $H_2$ and from $H_2$ to $y$. Hence there is a path $P$ from $x$ to $y$ which is internally disjoint to $G[H_1+x+y]$ and hence to $K$. We can replace the edge $xy$ in $K$ by the path $P$ to create a Kuratowski subgraph $K-xy+P$ in $G$. Contradiction.

My doubt is whether option 2 is really the definition of minimality or I misunderstand the proof and the author in fact uses some other properties to conclude $G$ contains a Kuratowski subgraph.

It really bothers me.

Thanks.

Answer 1

Minimality typically refers to something which has no subset or subgraph with a given property - corresponding to your first definition. Minimum typically refers to the smallest possible case which satisfies a property - corresponding to your second definition. A very important, and common distinction in graph theory.

An example of minimal would be: We have a vertex cover, removing any vertex from the set makes it no longer a cover. Hence it was a minimal vertex cover.

An example of minimum would be: We have a vertex cover which has exactly 5 vertices, every vertex cover that exists has 5 or more vertices, thus it is a minimum cover (and by extension also minimal).

EDIT:

From my understanding of the above proof, it would seem the author has used the opposite definitions. This is not common, but not unheard of. It is further confirmed by the use of the phrase "minimal vertex cut."

Answer 2

The statement "If $G$ is 3-connected then it has a minimal vertex cut $\{x,y\}$" is incorrect. If a graph is 3-connected, then the removal of any 2 vertices from the graph does not disconnect the graph. Hence, the size of any vertex cut is at least 3.

Getting to the definition of minimal. A structure is said to be minimal with respect to property $P$ if the structure satisfies property $P$ and no proper subset of the structure satisfies property $P$. Similarly, a structure $S$ is maximal with respect to property $P$ if it satisfies property $P$ and does not contain a proper superset which satisfies property $P$. A structure is minimum (with respect to $P$) if it has minimal cardinality, and it is maximum if it has maximal cardinality.

For example, a clique in a graph is a set of vertices that are pairwise adjacent. A maximal clique is a subset $W$ of vertices which cannot be enlarged to a larger clique. In other words, $W$ is a maximal clique in the graph if there is no clique $W'$ in the graph which properly contains $W$. The clique number of a graph, denoted by $\omega(G)$, is a clique in the graph of maximal size. Consider the cycle graph $C_7$ on vertex set $\{v_1,\ldots,v_7\}$. The set $\{v_1\}$ is a clique but is not a maximal clique since it is properly contained in a the larger clique $\{v_1,v_2\}$. The subset $\{v_1,v_2\}$ is a maximal clique (since it can't be enlarged to a larger clique) and it is also a maximum clique (since it is a clique of size $\omega(G)$). Similarly, $\{v_1,v_3\}$ is not a maximal independent set in $C_7$. A maximum independent set in $C_7$ is any independent set of size 3. In the graph on 8 vertices consisting of $C_7$ plus an isolated vertex $v_8$, the singleton $\{v_8\}$ is a maximal clique but not a maximum clique.

Here are some definitions where the concept of minimality arises. Recall that a graph on $n$ vertices is a tree if it is a connected graph having exactly $n-1$ edges. Equivalently, a graph $G$ is a tree if and only if it is a minimally connected graph. In other words, $G$ is a tree iff $G$ is connected and $G-uv$ is disconnected for each edge $uv$ of $G$. Also, a graph $G$ is a tree if and only if $G$ is a maximal acyclic graph, i.e. iff $G$ is acyclic and $G+uv$ contains a cycle for each non-edge $uv$. A component of a graph is defined to be a maximal connected subgraph (ie, it is any subgraph which cannot be made larger and still remain connected).