I am trying to construct a graph using $K_3$ graph. The graph $G$, obtained by adding vertices to $K_3$, should contain only one vertex with eccentricity two and the rest of the vertices with eccentricity three, and $K_3$ must be induced in $G$.
I can only add three, four or five vertices to $K_3$. I tried many examples but unable to do so. Kindly help. A little help or hint will be of great use to me. Thanks a lot for help.
Similarly, I have to draw a graph $G_1$ using $K_3$ by adding 7, 8 or 9 vertices such that the resultant graph contains only one vertex with eccentricity three and the rest of the vertices with eccentricity four.
My attempt to draw $G_1$ is as follows (but not successful). Vertices in red have eccentricity three and rest of the vertices have eccentricity four.
Well, actually I have no idea how can I turn my answer into a hint so I will go step by step. After each step, you can stop reading and think the rest for yourself. I will also write the eccentricities of vertices after each step.
Step 1: First of all, let us construct a graph where every vertex has eccentricity $3$. In order to do that, I consider the $n$-gons, where I started from $n = 5$. In a graph of $5$-gon, each vertex has eccentricity $2$. So I went for $n = 6$, where every vertex has eccentricity $3$. So we can continue from there:
Step 2: Now I thought how can we obtain $K_3$ without creating a vertex with eccentricity $2$ or $4$, i.e., by keeping all the eccentricities $3$. If we draw an edge inside the $6$-gon (a diagonal), then we won't have all the vertices having eccentricity $3$. So I added a new vertex outside as the following and got a $K_3$:
Step 3: Now, notice that all the vertices still has eccentricity $3$. Now we need to decrease one of the vertices' eccentricity by $1$ to have exactly one vertex with eccentricity $2$. At this point, I couldn't find a way of doing it by adding edges. But first I added an edge to have more than one vertices (three) of eccentricity $2$:
Step 4: And the last step. Our purpose here is to make eccentricity of two of the vertices $3$ again without changing the eccentricities of other vertices. Here, I couldn't find a way to do that by adding edges (maybe there is a way but I wasn't able to find it) so again I considered adding a vertex (also notice that with this one, we will have $5$ additional vertices to $K_3$). But while adding this one, I also considered vertices' paths of maximum length. Because I can't add a new vertex to a vertex where a path of length $3$ ends. We also have to add it so that vertices with eccentricity $2$ will have a longer path with length $3$. By considering these, I added the last vertex as the following:
And we are done.