MHB Proving Degrees of Vertices in Graph G

  • Thread starter Thread starter Amer
  • Start date Start date
  • Tags Tags
    Degrees Graph
AI Thread 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 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top