Question

Let G be an n-vertex graph with n ≥ 2 and δ(G) ≥ (n-1)/2. Prove that...

Let G be an n-vertex graph with n ≥ 2 and δ(G) ≥ (n-1)/2. Prove that G is connected and that the diameter of G is at most two.

Homework Answers

Answer #1

SOLUTION

Suppose that G is not connected. So, there exists two vertices u and v which lie in different components. Now, since both u and h have degree at least (n-1)/2, so the component in which they lie have at least (n-1)/2 + 1 vertices at least. Thus, total number of vertices in both the components is at least (n-1)/2 + 1 + (n-1)/2 + 1 = n+1.

Clearly this is a contradiction as there are n vertices in total. So, G must be connected.

Suppose G have diameter >2. So, there exists two vertices u and v such that uv path has length > 2. Thus, u and v share no common neighbours.

Now, since both u and h have degree at least (n-1)/2, so total number of neighbours of u and v combined are (n-1)/2 + (n-1)/2 = n-1

This implies that total number of vertices in the graph is n-1 + 2 = n+2 which is a contradiction. So, diameter must be <= 2.

Please Upvote

Thank you

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Graph Theory Let v be a vertex of a non trivial graph G. prove that if...
Graph Theory Let v be a vertex of a non trivial graph G. prove that if G is connected, then v has a neighbor in every component of G-v.
Let G be a graph or order n with independence number α(G) = 2. (a) Prove...
Let G be a graph or order n with independence number α(G) = 2. (a) Prove that if G is disconnected, then G contains K⌈ n/2 ⌉ as a subgraph. (b) Prove that if G is connected, then G contains a path (u, v, w) such that uw /∈ E(G) and every vertex in G − {u, v, w} is adjacent to either u or w (or both).
Let δ ≥ 2. Prove that every simple graph G satisfying δmin(G) ≥ δ and containing...
Let δ ≥ 2. Prove that every simple graph G satisfying δmin(G) ≥ δ and containing no triangles contains a cycle of length at least 2δ. Prove that this result is sharp by showing that we cannot guarantee the existence of a cycle of length at least 2δ + 1. Give a counterexample for each δ.
let G be a connected graph such that the graph formed by removing vertex x from...
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.
Let G be a simple graph with n(G) > 2. Prove that G is 2-connected iff...
Let G be a simple graph with n(G) > 2. Prove that G is 2-connected iff for every set of 3 distinct vertices, a, b and c, there is an a,c-path that contains b.
Prove the following bound for the independence number. If G is a n-vertex graph with e...
Prove the following bound for the independence number. If G is a n-vertex graph with e edges and maximum degree ∆ > 0, then α(G) ≤ n − e/∆.
Graph G is a connected planar graph with 1 face. If G is finite, prove that...
Graph G is a connected planar graph with 1 face. If G is finite, prove that there is a vertex with degree 1.
If G is an n-vertex r-regular graph, then show that n/(1+r)≤ α(G) ≤n/2.
If G is an n-vertex r-regular graph, then show that n/(1+r)≤ α(G) ≤n/2.
Prove or disapprove each of the following: (a) Every disconnected graph has an isolated vertex. (b)...
Prove or disapprove each of the following: (a) Every disconnected graph has an isolated vertex. (b) A graph is connected if and only if some vertex is connected to all other vertices. (c) If G is a simple, connected, Eulerian graph, with edges e, f that are incident to a common vertex, then G has an Eulerian circuit in which e and f appear consequently.
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.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT