2,118 views
0 votes
0 votes
a)The number of paths of length 4 between any two
adjacent vertices in K3,3 (bipartite graph)?

b) The number of paths of length 4 between any two
nonadjacent vertices in K3,3 (bipartite graph)?

1 Answer

0 votes
0 votes

as u have writeen it is K3,3 So I am assuming that it is complete bi-partite graph. In a complete bi-partite graph all vertices of one set are adjacent to all vertices of other set.right??
Now talking about question a)between two adjacent vertices there will be always a odd length path,even length path is not possible,why?? Because by 1 edge from one vertex you can go to another vertex of other set,then by taking 2nd edge you have to come back to one vertex of the same set,so by using even no of edges you can't have path between two adjacent vertices.So answer is 0 for a) question.
Now talking about question b)non-adjacent vertices are possible within same set,right??
Now for 1st edge, we have 3 choices possible,
next for 2nd edge, we have 3 choices possible,
next for 3rd edge, we have 3 choices possible,
next for 4th edge, we have only 1 choice possible as terminating vertex is fixed right? So no of paths=33
whats the answer?? Am i right??

Related questions

1 votes
1 votes
0 answers
1
CJ147 asked Aug 25, 2018
453 views
DIRAC’S THEOREM: If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit.The below ...
2 votes
2 votes
0 answers
2
someshawasthi asked Mar 27, 2023
498 views
The maximum number of edges possible in a graph G with 9 vertices which is 3 colourable is equal toA 24B 27C 36D None of the above