How to do these 3 questions ? Could someone please give me a detail explanation

Question

How to do these 3 questions ?

Could someone please give me a detail explanation of each questions ?

Many thanks

Let A be the adjacency matrix for a simple graph with n vertices and m edges. Express each of the following in terms of n and/or m: Suppose x and y are two vertices in the same connected component of a graph, and let k be the distance between them. Show that every walk of length k from x to y in the graph is a path. The complete bipartite graph Kn,n has 2n vertices, labelled say a1, a2...., an and b1, b2, ..., bn. and n2 edges, joining each vertex a1 to each vertex bj.

Explanation / Answer

2)

Let (V,E) represent the graph g

Let v,w ? V

Let the vertices be v0,v1,v2, and

Let the edges be e0,e1,en.

I would first shows that this graph has a walk if each vertex is incident to at least one edge. It means that a walk exists between two distinct vertices. From the definition of a path (a walk with no repeated vertices), it can be proven that if there exists a walk, then there exists a path.

i have modified my answer..To prove this i would start by defining what a walk and path are. A walk is an alternating sequence if vertices and edges begining and ending with a vertex where each vertex is incident to both the edge that precedes it and the edge that follows it and where the vertices that both precede and follow it are the end vertices of that edge. A walk is closed if its trivial or both it's first and last vertices are the same.

A path from v to w is a sequence of alternating vertices and edges where each vertex is incident to the edge that precedes it and incident to the edge that follows it.It has no repeated edges and the first and the last vertices are distinct.

from the definition of both walk and path,I can deduce that the path has to be an open walk because the vertices are distinct.

To prove that the walk from v to w is open and therefore a path,it would should not contain no cycle.

Using the theorem which states that a graph which has no isolated or pendant vertices,it has at least one simple circuit/cycle, I would prove that it contains no isolated or pendant vertices. let (V,E) be a graph with no isolated or pendant vertices.The length of any walk in this graph cannot exceed |V|-1 where |V| denotes the number of vertices of the graph ,since a walk of length m passes through m+ 1 distinct vertices.There fore there exists a walk in the graph v,x,...,w in the graph whose length m is greater thatn or equal to the length of every other walk in the graph. Now the final vertex w is incident to only one vertices since the graph contains a pendant vertices(It can not contain an isolated vertices because there would be no connection).This means that there cant be any looping back or cycle between v and w.There fore have proved that there exists an open walk from v to w.

3) b)

Suppose it were possible to construct a graph that fulfils condition (1) which is not Hamiltonian.

For a given n?3, let G be the graph with the most possible edges such that G is non-Hamiltonian which satisfies (1).

Although it does not contain a Hamilton cycle, G has to contain a Hamiltonian path (v1,v2,

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.