On a question of contractible graphs

392 Views Asked by At

A family $\mathcal{F}$ of graphs $G_1, G_2, \cdots, G_n ,\cdots$ is called contractible if

(1) The trivial graph, $\ast \in \mathcal{F}.$

(2) Any graph of $\mathcal{F}$ can be obtained from the trivial graph by finite series of contractible transformations $\{T_1, T_2, T_3, T_4\}$

where $T_1$: deleting of vertex $v$. A vertex $v$ of a graph $G$ can be deleted, if $N_G(v):= \{ u \in V(G): \text{ the edge }[uv] \in E(G)\} \in \mathcal{F}.$

$T_2:$ Gluing of a vertex $v$. If a subgraph $G_1$ of a graph $G$ is contractible, $G_1 \in \mathcal{F}$ the the vertex $v$ can be glued to the graph $G$ in such a manner that $N_G(v) =G_1,$

$T_3:$ deleting of an edge $[v_1v_2]$. The edge $[v_1v_2]$ of $G$ can be deleted if $N_G(v_1)\cap N_G(v_2)\in \mathcal{F}.$

$T_4:$ Gluing of an edge $[v_1v_2]$. Let two vertices $v_1$ and $v_2$ of a graph $G$ be non-adjacent. The edge $[v_1v_2]$ of $G$ can be glued if $N_G(v_1)\cap N_G(v_2)\in \mathcal{F}.$

Any graph $G \in \mathcal{F}$ is called a contractible graph.

Question: Is it true that any contractible graph with more than two vertices has at least two contractible vertices ( a vertex is called contractible if $N_G(v) \in \mathcal{F}$)?

Thank you in advance. Any help will be appreciated.