MHB Proving Degrees of Vertices in Graph G

  • Thread starter Thread starter Amer
  • Start date Start date
  • Tags Tags
    Degrees Graph
Click For Summary
In a graph G of order \(2n+1 \geq 5\), the degree of each vertex is either \(n+1\) or \(n+2\). The discussion revolves around proving that G must contain at least \(n+1\) vertices of degree \(n+2\) or at least \(n+2\) vertices of degree \(n+1\). An argument by contradiction is suggested, where assuming fewer vertices of each degree leads to a contradiction when counting edges. The conclusion is that the initial conditions cannot hold true without satisfying the degree requirements. Thus, the proof demonstrates the necessity of the stated vertex degree distribution in graph G.
Amer
Messages
259
Reaction score
0
The degree of every vertex of a graph G of order \[2n+1 \geq 5\] is either n+1 or n+2. Prove that G contains at least n+1 vertices of degree n+2 or at least n+2 vertex
 
Last edited:
Mathematics news on Phys.org
Is this question complete? It seems truncated.
 
The degree of every vertex of a graph G of order \[2n+1 \geq 5\] is either n+1 or n+2. Prove that G contains at least n+1 vertices of degree n+2 or at least n+2 vertex of degree n+1
 
Amer said:
The degree of every vertex of a graph G of order \[2n+1 \geq 5\] is either n+1 or n+2. Prove that G contains at least n+1 vertices of degree n+2 or at least n+2 vertices of degree n+1
Try using an argument by contradiction. Suppose that there are $x$ vertices of degree $n+1$, and $y$ vertices of degree $n+2$, and suppose that the result is false. Then $x\leqslant n+1$ and $y\leqslant n$. But $x+y=2n+1$. It follows that we must have $x=n+1$ and $y=n.$ By counting the number of edges in the graph, show that this leads to a contradiction.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Understanding a Graph Theory Proof
  • · Replies 3 ·
Replies
3
Views
983
Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
5K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad The number of intersection graphs of ##n## convex sets in the plane
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Classify the isomorphism of a graph
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
  • · Replies 10 ·
Replies
10
Views
3K
Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Finding the chromatic number of a graph with biconnected components
  • · Replies 1 ·
Replies
1
Views
2K
High School 4-colours theorem can be proved visually
  • · Replies 21 ·
Replies
21
Views
2K