Question

Let G = (X, E) be a connected graph. The distance between two vertices x and y of G is the shortest length of the paths linking x and y. This distance is denoted by d(x, y). We call the center of the graph any vertex x such that the quantity max y∈X d(x, y) is the smallest possible. Show that if G is a tree then G has either one center or two centers which are then neighbors

Answer #1

The distance between two connected nodes in a graph is the
length (number of edges) of the shortest path connecting them. The
diameter of a connected graph is the maximum distance between any
two of its nodes. Let v be an arbitrary vertex in a graph G. If
every vertex is within distance d of v, then show that the diameter
of the graph is at most 2d.

let G be a connected graph such that the graph formed by
removing vertex x from G is disconnected for all but exactly 2
vertices of G. Prove that G must be a path.

A spanning tree of connected graph G = (V, E) is an acyclic
connected subgraph (V, E0 ) with the same vertices as G. Show that
every connected graph G = (V, E) contains a spanning tree. (It is
the connected subgraph (V, E0 ) with the smallest number of
edges.)

Let
G be a simple graph with at least two vertices. Prove that there
are two distinct vertices x, y of G such that deg(x)= deg(y).

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.

(a) Let L be a minimum edge-cut in a connected graph G with at
least two vertices. Prove that G − L has exactly two
components.
(b) Let G an eulerian graph. Prove that λ(G) is even.

Exercise 10.5.4: Edge connectivity between two vertices.
Two vertices v and w in a graph G are said to be
2-edge-connected if the removal of any edge in the graph leaves v
and w in the same connected component.
(a) Prove that G is 2-edge-connected if every pair of vertices
in G are 2-edge-connected.

Let G=(V,E) be a connected graph with |V|≥2
Prove that ∀e∈E the graph G∖e=(V,E∖{e}) is disconnected, then G
is a tree.

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.

I.15: If G is a simple graph with at least two vertices, prove
that G has two vertices of the same degree.
Hint: Let G have n vertices. What are possible
different degree values? Different values if G is connected?

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 28 minutes ago

asked 37 minutes ago

asked 38 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago