coherent graph-minimum number of edges

687 Views Asked by At

A coherent graph with at least $3$ vertices is called doubled coherent,if it remains coherent even if we delete any edge.How many,at least,edges do such a graph with $n$ vertices has to have?

I think that it should have at least $n$ edges,or am I wrong?

1

There are 1 best solutions below

0
On

If your coherent graph $G$ has a degree-1 vertex $v$, removing the edge incident to $v$ makes it incoherent. Thus a doubled coherent graph cannot have a degree-1 vertex.

I assume you know that a tree has $n - 1$ edges. If $G$ has less than $n$ edges and no isolated vertex, then it is a tree, or one of its connected components is a tree. Otherwise, if each connected component of $G$ is not a tree, each component has at least as many edges as vertices, and in the end $G$ has at least $n$ edges or more. Since any tree (that is not an isolated vertex) has a degree-1 vertex, it follows that $G$ cannot be doubled coherent.

Note that there exist graphs on $n$ edges that are doubled coherent. For instance, the cycle graph $C_n$. Actually I think all the $n$-edges doubled coherent graphs on $n$ vertices are the cycle and the union of cycles (but that's just a thought, not a statement).