Question

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

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:

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 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 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 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 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 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: 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 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 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, 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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 14 minutes ago

asked 16 minutes ago

asked 41 minutes ago

asked 52 minutes ago

asked 55 minutes ago

asked 59 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago