Register

Graph Theory Doubt

• retagged by
1,206 views

1 Answer

1 1 vote
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.
Voting & Accepting an answer helps improve the community
← Previous · MadeEasy Subject Tes...Next → · ME Test Series
← Previous in category · #treeNext in category → · Self doubt
Position:
Show:

Related questions

0 0 votes
1 1 answer
402
402 views
Nisarga k asked Mar 6, 2025
402 views
Unacademy practice question based on graph theory
Which of the following will be an upper bound for minimum degree of a graph with10 vertices.(a) 9 (b) 8 (c) 7 (d) 6
0 0 votes
0 0 answers
1.4k
1.4k views
Prince Sindhiya asked Jan 2, 2019
1,418 views
Zeal Test Series 2019: Graph Theory - Degree Of Graph
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such tha...
3 3 votes
3 3 answers
2.0k
2.0k views
Tushar Shinde asked Jan 13, 2016
1,991 views
Ace Test Series: Graph Theory - Degree Of Graph
How to PROVE S2 is correct??Consider the statements $S_1$ ) In any simple graph with more than one vertex, there must exist at-least $2$ vetices of the same degree $...
1 1 vote
1 1 answer
384
384 views
GO Classes asked Oct 16, 2024
384 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 11
For which of the following does there exist a simple undirected graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ satisfying the specified conditions?$\text{G}$ has $3$ compone...