# In a certain country ,$100$ roads lead out of each city and one can travel along those roads from one city to the other

In a certain country ,$$100$$ roads lead out of each city and one can travel along those roads from one city to any other . One road is closed for repair work . Prove that one can still get from any city to another . The solution given on the book is as follows:

If road $$AB$$ has closed then it is enough to prove that we can still get from $$A$$ to $$B$$. If this were not true, then in the connected component containing $$A$$ all the vertices other than $$A$$ would be even . The situation of having exactly one odd vertex in a connected component contradicts the statement "A graph must have an even number of odd vertices"

However, I am not getting the idea of the solution ...I dont get what does it mean by saying " If this were not true, then in the connected component containing $$A$$ all the vertices other than $$A$$ would be even " ...the path from A to B is deleted so...the degree of B is also odd...so, how does they draw this conclusion ...

• If one cannot go from $A$ to $B$, then $B$ is not in the connected component of $A$. Commented Apr 14, 2022 at 13:19

Let $$G$$ be the graph in question.

Suppose if we closed $$AB$$ we could not get from $$A$$ to $$B$$.

That means we could divide $$G$$ into two separate components: one containing $$A$$ and one containing $$B$$, just by deleting $$AB$$ (that is: closing the road between $$A$$ and $$B$$).

Anyway, suppose we could do this.

Let $$S$$ and $$T$$ be collections of vertices of the graph $$G$$, which are joined by a bridge $$AB$$, so that $$A$$ is a vertex of $$S$$ and $$B$$ is a vertex of $$T$$.

(In this context, a "bridge" is an edge of a graph that, if you remove it, separates the graph into two disconnected components.)

Thus when $$AB$$ is deleted, and we can no longer get from $$A$$ to $$B$$, that means $$S$$ and $$T$$ make two separate graphs.

Before we remove edge $$AB$$ (that is, close the road):

• All vertices in $$S$$ are even, including $$A$$ which is incident to the bridge $$AB$$.

• All vertices in $$T$$ are even, including $$B$$ which is incident to the bridge $$AB$$.

But when you delete $$AB$$:

• all the vertices in $$S$$ except $$A$$ are even, while $$A$$ is odd.

• all the vertices in $$T$$ except $$B$$ are even, while $$B$$ is odd.

Hence $$S$$ and $$T$$ are both graphs which do not have an even number of odd vertices.

Because that cannot happen, it cannot be the case that deleting $$AB$$ causes $$S$$ and $$T$$ to be disconnected.

Hence you must be able to get from $$A$$ to $$B$$ without needing to use the road $$AB$$.

• Thank you so much! But can you please explain how after deletion of $AB$ we do get two connected components....I mean whats the gurantee that the graph resulting will be a connected graph component of the original graph...
– user992622
Commented Apr 14, 2022 at 14:17
• $G$ is a connected graph, which means you can get from any node (city) to any other node. Suppose you delete $AB$ and you can't now get from $A$ to $B$ via another route. That means the subgraphs containing $A$ and $B$ are disconnected, which means they are separate graphs in their own right. The fact that you can't disconnect $A$ and $B$ by removing one edge (that is, "closing one road") means there must be another route from $A$ to $B$ (travelling via other cities, probably) which means that you can't disconnect the graph by deleting one edge. Commented Apr 14, 2022 at 14:38
• ....How after deletion of $AB$ we do get two graphs $S$ and $T$ such that all of them have even vertices except $A$(in $S$ ) and $B$ (in $T$) as they are only the odd vertices...but if $S$ has $A$ and $B$ both then it has an even number of odd vertices ...are u insisting on that $S$ should exclude $B$ but then again all other vertices in $S$ will have $99$ edges and then it depends upon the number of vertices in S if it is even then its possible but if odd then it's not possible....I am not quite getting this....
– user992622
Commented Apr 14, 2022 at 14:41
• $S$ does not have both $A$ and $B$, $S$ just has $A$. 1) We want to prove you can't disconnect $G$ into two parts, one containing $A$ and one containing $B$. (Because if you did that, then you would not be able to get from $A$ to $B$ without using the closed road $AB$.) 2) So we suppose the opposite, that you can disconnect $G$ into two parts by closing the road $AB$, and from that we prove something impossible. (In this case, the "impossible" thing we prove is that we have $2$ graphs, both with an odd number of odd vertices.) Continued ... Commented Apr 14, 2022 at 14:49
• @Franklin I have added the "reductio ad absurdum" construction, the "suppose the opposite, and from that prove an impossibility" to the answer I originally gave. Commented Apr 14, 2022 at 15:18