With `ConvexHullMesh` there are **missing edges** at the boundary. The **graph below colors edges randomly but** as we see there are **many supposed edges at the boundary** that are actually the **same edge** as they have the **same color**. They are simply long edges that traverse the vertices due to the imposed geometry for the graph.

[![enter image description here][2]][2]

With the **code below** **all edges are included**. Note that randomly coloring the edges a few times, accidental same color adjacent edges are removed.


[![enter image description here][3]][3]


----------------------------------
**Outline**

 - **Issue with application of ConvexHull**

 - **Solution to OP's question**

--------------------------------

### Issue with application of ConvexHull

**TL;DR :** The line segments from `ConvexHull` seem to pass through points that rest on the same line. Hence there are missing edges when one just adds the line segments.

From what I tested, the convex hull mesh does not seem to produce all the edges between graph vertices. See the image below that shows the added line segments from the convex hull:

 {GraphEmbedding[g] // ConvexHullMesh // MeshPrimitives[#, 1] & // 
 Map[{RandomColor[], #} &], GraphEmbedding[g] // Map[Point]} // 
 Catenate // Graphics

[![enter image description here][1]][1]

This can also be checked with the graph:

 HighlightGraph[new, Style[#, RandomColor[]] & /@ EdgeList@new]



[![enter image description here][2]][2]



There are colors that traverse vertices at the boundary.

Also 

 KVertexConnectedGraphQ[new, 2]

`(* False *)`

which OP does not seem to want.

---------------------------

### Solution to OP's question

**TL;DR**: Extract degree 1 vertices, use [`FindCurvePath`](https://reference.wolfram.com/language/ref/FindCurvePath.html) and [`PathGraph`](https://reference.wolfram.com/language/ref/PathGraph.html) to connect them and then add them to the original graph with a graph position to geometrical postion mapping


The vertices at the boundary are all degree one vertices. They can be extracted using:

**Note:** (`…=\[Ellipsis]`)

 boundary…vertices = 
 VertexList[g, _?(VertexDegree[g, #] == 1 &)]

Their geometric positions can be found using the rule:

 VertexPos = Thread[VertexList[g] -> GraphEmbedding[g]];

Note: (`⎵=\[UnderBracket]`)

 boundary…vertices⎵positions = 
 boundary…vertices /. VertexPos;

One may order these vertices along a path using [`FindCurvePath`](https://reference.wolfram.com/language/ref/FindCurvePath.html)

 path…ordering = 
 FindCurvePath[boundary…vertices⎵positions];

 path = boundary…vertices⎵positions[[path…ordering[[1]]]]

 
Then one may construct edges from those ordered points using [`PathGraph`](https://reference.wolfram.com/language/ref/PathGraph.html) and [`EdgeList`](https://reference.wolfram.com/language/ref/EdgeList.html). Note that we first had to order the edges before using `PathGraph`.

 path⎵edges = path // PathGraph // EdgeList;

Those are written as spatial points we have to convert them back to vertex positions by inverting VertexPos above. We then add those edges to the original graph:

 completed…graph = EdgeAdd[g, path⎵edges /. Reverse /@ VertexPos]

We can check the result with:

 HighlightGraph[completed…graph, 
 Style[#, RandomColor[]] & /@ EdgeList@completed…graph]

**Note**: some edges at the boundary might randomly have a similar color, evaluate the code again to change colors and check that the edges no longer have the same color. 


[![enter image description here][3]][3]


 KVertexConnectedGraphQ[completed…graph, 2]

`(* True *)`



 


 [1]: https://i.sstatic.net/0wMgn.png
 [2]: https://i.sstatic.net/mf768.png
 [3]: https://i.sstatic.net/qWtqf.png