Introduction to Graph Theory Exercises
in Graph Theory
108 views
0 votes
0 votes

This is the problem snapshot

in Graph Theory
by
1 1
108 views

5 Comments

$(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
1
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
0
$\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
0
@ankit Can you please elaborate a little bit. I did not understand
0
0
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
0

Subscribe to GO Classes for GATE CSE 2022

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
2
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true