0 votes 0 votes If there is a graph such that there is a unique path between any pair of vertices. The graph is a ________ Mesh Grid Tree Bipartite graph Unknown Category uttarakhand-asst-prof-2018 graph-theory data-structures + – gatecse asked Mar 2, 2018 • edited Mar 6, 2018 by go_editor gatecse 347 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes (c) Tree If there exist more than one unique path for a pair of vertices then it will form a circuit which violates the condition. Tree : a connected graph with no circuits Bipartite graph : a graph with no circuits of odd size Mk Utkarsh answered Mar 2, 2018 • edited Mar 3, 2018 by Mk Utkarsh Mk Utkarsh comment Share Follow See all 3 Comments See all 3 3 Comments reply Mamta Satywali commented Mar 3, 2018 reply Follow Share Adding on(Might be useful to others)- Why not option D? Every tree(which is a bipartite graph) has unique path b/w every pair of vertices but NOT all bipartite graphs have unique path b/w every pair of vertices. eg-K3,3 3 votes 3 votes Mk Utkarsh commented Mar 3, 2018 reply Follow Share excellent point :) 1 votes 1 votes ankitgupta.1729 commented Mar 3, 2018 reply Follow Share One more way to prove D as wrong :- A graph is bipartite iff it has even length cycle...Means if a graph has even length cycle then it will be bipartite and if a graph is bipartite then it will have even length cycle... So Every Bipartite graph has even length cycle , It means there are 2 paths are possible between every pair of vertices as clockwise and anticlockwise in the cycle... 1 votes 1 votes Please log in or register to add a comment.
