Which graphs $G$ in which any circle is an edge separator maximize $||G||$ for fixed |G|?

Question

Questions

1. Is my solution to the following exercise correct?
2. The exercise gives the following hint: Consider the complement of a spanning tree. How would you come up with that hint yourself? Do you know other problems that use that "trick"?

Exercise

Let $n\geq 2$. Let $G$ be a connected graph with $n$ vertices and the following property: For every circle $C$ in $G$ the graph $G-E(C)$ is not connected. How many edges can $G$ at most have?

My solution

Claims:

1. The graph $G$ has at most $2n-3$ edges.
2. For every $n\geq 2$ there exists a graph with above property.

Proof:

1. First, we show that the graph $G$ has at most $2n-3$ edges.

Lemma: Any connected, finite graph $G$ has a spanning tree $(T, r)$ with root $r$ such that $N_T(r)= N_G(r)$.
Proof: We prove the lemma by induction on $|G|$. The base case is trivial.
Let $G$ be a connected graph with $n\geq2$ vertices. Let $v \in V(G)$. With the induction hypothesis the graph $G-v$ has a spanning tree $(T, r)$ with root $r$ such that $N_{T}(r)= N_{G-v}(r)$. If $vr \in E(G)$, then $T+vr$ is the desired spanning tree for $G$. Otherwise, choose any $x \in G$ with $xr \in G$. Such vertex $x$ exists because $G$ is connected. Then $T+xr$ is the desired spanning tree of $G$. $\square$

Now, let $G$ be a graph with the properties from the exercise.
Let $(T, r)$ be a spanning tree of $G$ with root $r$ such that $N_T(r)= N_G(r)$. Then the complement $G':=G-E(T)$ is a forest. Otherwise one could delete a circle $C \in G'$, and $G-E(C)$ would remain connected, contradiction. Owing to the choice of $T$, the equality $||G'||=||G'-r||$ holds. As a forest is made up of trees as its connected components, we obtain $||G'-r|| \leq n-2$. Hence, we have shown $||G||=||T||+||G'|| =||T||+||G'-r|| \leq 2n-3$.

2. Second, for any $n\geq 2$ we give a connected graph $G_n$ with the desired properties.

If $n=2$, take a path of length one.
If $n\geq 3$, we obtain the graph $G_n$ recursively:
For $n=3$ let $G_3$ be a triangle with vertices $v_1,v_2,v_3$.
For $n=i+1$ set $G_{i+1}$:

• $V(G_{i+1})= V(G_{i})\cup \{x\}$ where $x \notin V(G_{i})$
• $E(G_{i+1})= E(G_{i})\cup \{v_1x, v_2x\}$

One checks that for any $n \geq 3$ the graph $G_n$ has the desired properties. $\square$

Answer 1

Mentioned in comment : Your inductive step is not valid. I will offer a simple proof that relies on knowing Prim's or Dijkstra's algorithm.

Claim : For any finite connected simple graph G, and any vertex $v \in V(G) $ there exists a spanning tree $T$ of $G$ with $N_T(v) = N_G(v)$.

Proof :

Given vertex $v$ assign weight 0 to all edges incident to $v$ in $G$. Assign weight 1 to all other edges.

(Dijkstra)

I claim that Dijkstra's algorithm will always produce such a tree, since each edge $uv$ for $u\in N_G(v)$ can be added without creating a cycle.

(Prim)

Run prim's algorithm beginning with $S=\{v\}$ as the first choice of vertex. The algorithm always chooses the cheapest edge from $S$ to $V-S$, and thus $uv$ is added to the spanning tree for each $u \in N_{G}(v)$

By the correctness of the algorithms, such a tree exists.

===================================

Now, to prove the initial statement, Let $T$ be a spanning tree such that $N_T(v)= N_G(v)$ for some $v\in V(G)$. Also note that adding any edge in $E(G)-E(T)$ creates a cycle, which by definition is an edge separator. This implies that $G-E(T)$ is At BEST a tree, since, each edge of $G-E(T)$ is incident on some cycle in $G$ and the other edges on that cycle are now in $E(T)$ and thus not in $G-E(T)$. But, we also know that $v$ is an isolated vertex in $G-E(T)$, and so $G-E(T)$ is a forest with at most two components. So, all together, the know that the graph had at most $2n-3$ edges.

For the tightness bound, you can simply set $G$ to be the path graph on $n-1$ vertices, union an additional vertex adjacent to each vertex on the path.