Register

Graph Theory Doubt

• retagged by
798 views

1 Answer

1 votes
1 votes
Yes, this is true.

Assume it is not true - it means that those two vertices belong to two different components. If they belong to two different components, then they are the only vertex in the component with an odd degree and we know that since a component is connected, the number of odd degree vertices have to be even. So, such components cannot exist and hence, both the vertices have to belong to the same component and hence, there exists a path between them.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
0 answers
3
dd asked Jul 4, 2017
450 views
Graph Degree sequence : Bondy and Murty : $1.1.16$
Let $d = (d_1,d_2,\dots, d_n)$ be a nonincreasing sequence of nonnegative integers, that is, $d_1 \geq d_2 \geq · · · \geq d_n \geq 0$. Show that: there is a loopless graph with degree sequence d if and only if $\sum_{i=1}^{n}d_i$ is even and $d_1 \leq \sum_{i=2}^{n}d_i$
Let $d = (d_1,d_2,\dots, d_n)$ be a nonincreasing sequence of nonnegative integers, that is, $d_1 \geq d_2 \geq · · · \geq d_n \geq 0$. Show that:there is a loopless g...
User Avatar
0 votes
0 votes
1 answer
4
admin asked Apr 1, 2020
572 views
NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 7
The number of the edges in a regular graph of degree $’d’$ and $’n’$ vertices is Maximum of $n,d$ $n+d$ $nd$ $nd/2$
The number of the edges in a regular graph of degree $’d’$ and $’n’$ vertices is Maximum of $n,d$$n+d$$nd$$nd/2$
User Avatar
Link Copied!