What are all the minimal prime extensions of the graph $P_3$?

98 Views Asked by At

I am struggling a little bit with the concept of minimal prime extensions of graphs and I was wondering if my solution to one of the exercises in the lecture notes is correct. In my lecture notes a prime graph is defined as a graph which has no non-trivial modules. A prime extension of a non-prime graph $G$ is a graph $H$, which is prime and contains $G$ as an induced subgraph. A minimal prime extension of a graph $G$ is a graph $H$ which is a prime extension of $G$ and every proper induced subgraph of $H$ either does not contain $G$ or is not prime. The question is to find all the minimal prime extensions of $P_3$, my attempted solution is below.

Let $\{a,b,c\}$ be the 3 vertices in $P_3$ where $b$ is the middle vertex. Now take some prime extension $H$ of $P_3$ and I will show that it must contain $P_4$ as an induced subgraph. Let $A=\{a,c\}$ and $B=\{b\}$, and apply repeatedly the following 2 operations as long as possible to any vertex $x$ not in $A$ or $B$: if $x$ has a non-neighbour in $A$ and is a neighbour of every vertex in $B$, add it to $A$, similarly if $x$ has a non-neighbour in $B$ and is a neighbour of every vertex in $A$, add it to $B$.

After these operations are done, there must exist a vertex $y$ outside of $A$ such that it has a neighbour $u$ and a non-neighbour $v$ in $A$, otherwise $A$ would be a non-trivial module in $H$ contradicting the fact that $H$ is prime. The vertex $y$ must also be outside of $B$, because by construction every vertex in $B$ has to be a neighbour of every vertex in $A$, which $y$ is not. Furthermore $y$ must have a non-neighbour in $B$ call it $w$, otherwise $y$ would be in $A$.

The graph induced by $A$ in the complement of $H$ will be connected, as every time we add a vertex to $A$ it has a non-neighbour in $A$ and thus a neighbour in the complement, and $a$ and $c$ are adjacent in the complement of $H$. In particular $u$ and $v$ are connected in the complement of $H$, so there exists a path between them in the complement, which is a sequence of non-neighbours between $u$ and $v$ in $A$ in $H$.

Since $y$ is a neighbour of $u$ and non-neighbour of $v$ in $H$, there exist two non-neighbours in $A$ in the sequence defined above, call them $u'$ and $v'$ such that $u'$ is a neighbour of $y$ and $v'$ is not. By construction $w$ is adjacent to both of these, thus $\{v', w, u' ,y\}$ induce a $P_4$ subgraph in $H$, which is a prime graph that contains $P_3$ as an induced subgraph. So the only minimal prime extension of $P_3$ is $P_4$, as any other prime extension would contain $P_4$ as an induced subgraph, making it non-minimal.