1
$\begingroup$

Let $G$ be a 2-connected graph, $G$ is minimally 2-connected if for any $e \in E(G)$, $G-e$ is not 2-connected. For each number $n$, construct a minimally 2-connected graph with a vertex of degree at least $n$.

I tried using the bipartite and similar graphs to construct such examples. But I never succeeded in finding them. Is there a clever way to construct such graphs? Thanks.

$\endgroup$
1
$\begingroup$

Consider the complete bipartite graph $K_{n,2}$. Removing any edge from this graph will always leave one vertex $v$ having degree 1; after removing the edge, removing the single vertex adjacent to $v$ will disconnect the graph.

$\endgroup$
1
$\begingroup$

For any $n$, take $\lceil \frac n2 \rceil$ copies of $C_5$, the cycle graph with five vertices. Then, choose a vertex in each of the copies, and identify all these vertices. The resulting vertex has degree $n$ or $n + 1$; if you remove any edge from this graph, it remains connected, but by removing a different edge from the same cycle you can always disconnect it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.