Graph theory: plex and clique

Question

How do a 2-plex relates to a 2-clique? I think that being a 2-plex means that is also a 2-clique but i don't know how to prove it. Thanks,

Answer 1

Assuming that you mean these definitions of a $k$-plex and $k$-clique...

...you should first be informed that these are not very standard, and basically no graph theorist uses this terminology (in particular, most people will take "$k$-clique" to mean "clique on $k$ vertices")...

...but yes, except in small cases. If we define a $k$-plex in a graph $G$ to be an $n$-vertex subgraph with minimum degree $n-k-1$ (with respect to the subgraph), and a $k$-clique to be a subgraph in which any two vertices are at distance at most $2$ (with respect to all of $G$), then any $2$-plex on at least $5$ vertices will be a $2$-clique.

If $v,w$ are any two vertices in a $2$-plex, then either $vw$ is an edge, or $v$ and $w$ each have at most one other vertex in the $k$-plex they're not adjacent to. If there are at least three other vertices in the $k$-plex, then one might not be adjacent to $v$, and another might not be adjacent to $w$, but the third is just right.

As a result, in a $2$-plex on at least $5$ vertices, any two vertices are at distance $1$ or $2$, and so the $2$-plex is a $2$-clique.

On the other hand, a $2$-plex on $3$ or fewer vertices might not have any edges, and a $2$-plex on $4$ vertices might just be a path of length $3$. Such subgraphs are not $2$-cliques on their own; they might become $2$-cliques by connections outside of the subgraph, but they also might not.

In general, the same argument shows that a $k$-plex on at least $2k+1$ vertices is always a $2$-clique. Moreover, since we don't use any edges outside the subgraph, it is not just a $2$-clique but (borrowing more of the weird terminology) a $2$-clan.