0 votes 0 votes This is the problem snapshot Graph Theory graph-theory graph-connectivity discrete-mathematics + – AngshukN asked May 22, 2022 AngshukN 378 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply ankitgupta.1729 commented May 26, 2022 reply Follow Share $(a)$ can be proved by contradiction. Assume that induced subgraph $<V(G_1) \cup \{v\}>$ of $G$ is not connected. Since, $v$ is a cut-vertex, it means $G-v$ creates more than one components and say, one of those components is $G_1.$ It means there exist a vertex $u$ in $G_1$ such that edge $uv$ is in the edge set of $G.$ So, there is a path between component $G_1$ and vertex $v.$ Now, component $G_1$ must be connected because if it is not connected then graph $G$ would also not be connected which contradicts our assumption. So, $<V(G_1) \cup \{v\}>$ of $G$ must be connected. For $(b),$ could you please define the block ? 1 votes 1 votes AngshukN commented May 27, 2022 reply Follow Share Hey @Ankit thanks for your comment. Block is basically a maximal inseparable subgraph of the graph. Inseparable graph is a graph with no cut vertices. So basically removal of a set of cut vertices would create a set of blocks of the graph. 0 votes 0 votes ankitgupta.1729 commented May 29, 2022 reply Follow Share $\Delta\Delta_v \Delta$ could be a counterexample. Here $v$ is a cut vertex and consider $<V(G_1) \cup \{v\}>$ be a graph of left two triangles which is not a block of $G$ because it is separable. 0 votes 0 votes AngshukN commented May 29, 2022 reply Follow Share @ankit Can you please elaborate a little bit. I did not understand 0 votes 0 votes ankitgupta.1729 commented May 30, 2022 reply Follow Share Consider delta symbol $\Delta$ as triangle. Now, suppose, there is a graph $G$ as $\Delta \Delta_v \Delta$ which means left $2$ triangles are connected with one triangle in the right side by a cut-vertex $v$ (removing $v$ disconnects the graph though one more cut vertex is there in graph $G$ as there is no restriction on the number of cut vertices in $G$ but $G$ must have a cut vertex labeled as $v$) Now, suppose $G-v$ has one component, say, $G_1$ as $\Delta$/ which can be obtained by removing $v$, Now induced subgraph $<V(G_1) \cup \{v\}>$ will be $\Delta \Delta_v$ which is a subgraph of $G$ and it is separable by a cut vertex, say $u$ denoted as $\Delta_u \Delta_v$ and hence, not a block. 0 votes 0 votes Please log in or register to add a comment.