0
$\begingroup$

Let $G(V,E)$ be a connected undirected graph (undirected=easier), such that, $S_x=V\setminus\{x\}, \forall x \in V$ is a subset of vertices of G. Then the induced subgraph $G[S_x]$ is the graph whose vertex set is $S_x$ and whose edges set consists of all of the edges in $E$ that have both endpoints in $S_x$.

Prove that a graph $G(V,E)$ has a Hamiltonian path (not necesarily a cycle) if the induced subgraphs $\forall x \in V, G[S_x]$ have at most 2 connected components.

$\endgroup$
7
  • $\begingroup$ What is your thinking $\endgroup$
    – Shubham Johri
    Commented Dec 27, 2020 at 11:02
  • $\begingroup$ What do you mean? $\endgroup$
    – yugikaiba
    Commented Dec 27, 2020 at 11:03
  • $\begingroup$ Welcome to MSE ^_^ What have you tried? Do you have any ideas? Once we have a better idea of exactly where you're struggling, we can help you better $\endgroup$
    – Chris Grossack
    Commented Dec 27, 2020 at 11:04
  • $\begingroup$ You need to add your own efforts to solve the question and where you are stuck. Or your question might get downvoted and closed. $\endgroup$
    – Shubham Johri
    Commented Dec 27, 2020 at 11:05
  • $\begingroup$ My thoughs. math.stackexchange.com/questions/3963112/… $\endgroup$
    – yugikaiba
    Commented Dec 27, 2020 at 11:07

1 Answer 1

Reset to default
1
$\begingroup$

Below is probably the simplest counterexample.

enter image description here

$\endgroup$
1
  • $\begingroup$ Thank you for answering! $\endgroup$
    – yugikaiba
    Commented Dec 27, 2020 at 12:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .