Question

Let G be the graph having 3 vertices A, B and C. There are five edges...

Let G be the graph having 3 vertices A, B and C. There are five edges connecting A and B and three edges connecting B and C. Solve the following:

1) Determine the number of paths from A to B

2) Determine the number of different trails of length 6 from A to B

Math   Statistics-And-Probability   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

1. A Path in a graph is a sequence of edges which joins a sequence of vertices that are all distinct. Here there are 5 edges connecting A and B. Ths there are 5 paths from A to B.

2. A Walk in which no edge is repeated then we get a trail. Vertex can be repeated. Here edges not repeat. Thus the number of trails of length 6 are:

4 edges between A and B are chosen and the remaining 2 between B and C are chosen.

If the edges are distinct.

case(1): A-B-A-B-C-B: number of trails= 5*4*3*2*3*2=720

case(2): A-B-C-B-A-B: number of trails= 5*4*3*2*3*2= 720

Thus total number of trails is 1440.

If the edges are not distinct:

then the answer is:

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let G = (V,E) be a graph with n vertices and e edges. Show that the...
Let G = (V,E) be a graph with n vertices and e edges. Show that the following statements are equivalent: 1. G is a tree 2. G is connected and n = e + 1 3. G has no cycles and n = e + 1 4. If u and v are vertices in G, then there exists a unique path connecting u and v.
Let G be a connected simple graph with n vertices and m edges. Prove that G...
Let G be a connected simple graph with n vertices and m edges. Prove that G contains at least m−n+ 1 different subgraphs which are polygons (=circuits). Note: Different polygons can have edges in common. For instance, a square with a diagonal edge has three different polygons (the square and two different triangles) even though every pair of polygons have at least one edge in common.
Let G be an undirected graph with n vertices and m edges. Use a contradiction argument...
Let G be an undirected graph with n vertices and m edges. Use a contradiction argument to prove that if m<n−1, then G is not connected
A graph is called planar if it can be drawn in the plane without any edges...
A graph is called planar if it can be drawn in the plane without any edges crossing. The Euler’s formula states that v − e + r = 2, where v,e, and r are the numbers of vertices, edges, and regions in a planar graph, respectively. For the following problems, let G be a planar simple graph with 8 vertices. Find the maximum number of edges in G. Find the maximum number of edges in G, if G has no...
Let there be planar graph G with 12 vertices where every vertices may or may not...
Let there be planar graph G with 12 vertices where every vertices may or may not be connected by an edge. The edges in G cannot intersect. What is the maximum number of edges in G. Draw an example of G. What do you notice about the faces and the maximum number of edges?
Consider the complete bipartite graph Kn,n with 2n vertices. Let kn be the number of edges...
Consider the complete bipartite graph Kn,n with 2n vertices. Let kn be the number of edges in Kn,n. Draw K1,1, K2,2 and K3,3 and determine k1, k2, k3. Give a recurrence relation for kn and solve it using an initial value.
Graph Theory. A simple graph G with 7 vertices and 10 edges has the following properties:...
Graph Theory. A simple graph G with 7 vertices and 10 edges has the following properties: G has six vertices of degree a and one vertex of degree b. Find a and b, and draw the graph. Show all work.
30. a) Show if G is a connected planar simple graph with v vertices and e...
30. a) Show if G is a connected planar simple graph with v vertices and e edges with v ≥ 3 then e ≤ 3v−6. b) Further show if G has no circuits of length 3 then e ≤ 2v−4.
Suppose that G is a graph and a and b are vertices in G such that...
Suppose that G is a graph and a and b are vertices in G such that a does not =b. Prove that if there is a walk from a to b, then there is a path from a to b. A walk in the graph is a sequence of vertices where there is an edge between each pair a_i and a_(i+1). The length of a walk is n. If a_0=a_n, ie if the walk begins and ends at the same...
Consider the graph G = K4 consisting of a single undirected cycle (a, b, c, d,...
Consider the graph G = K4 consisting of a single undirected cycle (a, b, c, d, a) of length 4. Let n be a positive integer. Give an explicit formula for the number of paths in G of length n from a to b.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT