Proving Vertex Count in a Graph with Girth 5 and Minimum Degree d

  • Thread starter MathematicalPhysicist
  • Start date
  • Tags
    Graph
In summary, a graph with girth 5 and all vertices having degree >=d must have at least d^2+1 vertices. Equality can hold, but it is not a strict bound. This can be proven by showing that for each node A, there are at least d*(d-1) + d + 1 = d^2 + 1 nodes that are not adjacent to A. This can also be proved by induction on d.
  • #1
MathematicalPhysicist
Gold Member
4,699
371
The girth of a graph is the length of the smallest polygon in the graph. Let G be graph with girth 5 for which all vertices have degree >=d. Show that G has at least d^2+1 vertices.
Can equality hold?

I am not sure, but how do I use the fact that the girth of G is 5, the only thing it tells me is that there are at least 5 vertices?

Should I prove this statement by induction on d?

What I did think of is using the fact the summing the degrees over all the vertices gives us that (1) 2|E|>=d*N, where N is the number of vertices and E is the set of edges of G.
Now if I show that |E|>=(d^3+d)/2, and this is not a strict bound, then I prove it, but it seems even difficult than a proof by induction which I am not sure how to do also.

Any hints?
 
Physics news on Phys.org
  • #2
Well, if the graph has girth 5, that means that if nodes A and B are adjacent, then B cannot be adjacent to any other node that A is adjacent to. Additionally, if B and C are both adjacent to A, then the intersection of the nodes adjacent to B and C is just A.

If a given node A connects to d other nodes, then there are (at least) d*(d-1) nodes other than A that are adjacent to nodes adjacent to A. And A can't connect to any of those. So for each node A in the graph, there are at least d*(d-1) nodes that are not adjacent to A. And there are at least d nodes that are adjacent to A. And then there's A itself. Adding all these nodes together, you get d*(d-1) + d + 1 = d^2 + 1.
 
  • #3
Thanks, I got to this same reasoning after someone else gave me a hint on how to solve this from another forum.
 

1. How do you define the vertex count in a graph with girth 5 and minimum degree d?

The vertex count in a graph with girth 5 and minimum degree d refers to the total number of vertices or nodes present in the graph. In this specific case, the graph must have a girth (or cycle length) of at least 5 and each vertex must have a minimum degree of d, meaning that it must be connected to at least d other vertices in the graph.

2. What is the significance of girth and minimum degree in proving vertex count in a graph?

The girth and minimum degree play important roles in determining the vertex count in a graph. The girth determines the minimum cycle length in the graph, which can help identify any potential bottlenecks or limitations in the connectivity of the graph. The minimum degree ensures that each vertex has a sufficient number of connections, which can impact the overall structure and complexity of the graph.

3. Can a graph have a girth of 5 and minimum degree d but still have different vertex counts?

Yes, it is possible for a graph to have a girth of 5 and minimum degree d while having different vertex counts. The vertex count depends on the specific arrangement and connections of the vertices in the graph, which can vary even with the same girth and minimum degree requirements.

4. How can one prove the vertex count in a graph with girth 5 and minimum degree d?

There are various techniques and algorithms that can be used to prove the vertex count in a graph with girth 5 and minimum degree d. One approach is to use induction, where we start with a simple graph and gradually add more vertices and edges while ensuring that the girth and minimum degree requirements are met. Another approach is to use properties of the graph, such as its adjacency matrix or degree sequence, to calculate the vertex count.

5. What are the real-world applications of proving vertex count in a graph with girth 5 and minimum degree d?

Proving vertex count in a graph with girth 5 and minimum degree d can have practical applications in various fields, such as computer networking, social network analysis, and transportation planning. It can help in identifying the critical nodes or bottlenecks in a network, analyzing the connectivity of social groups or communities, and optimizing transportation routes and schedules.

Similar threads

MHB Minimum Degree of a Random Graph (Probabilistic Method)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Girth of $H_d$ Hypercube Graph: Proving $4$ by Induction
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
MHB Proving Turan's Theorem (Dual Version) and its Implications for $ex(n, K_{p+1})$
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB A Subset of a Graph with No Perfect Matching
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Proving the symmetry of self complementary graphs with n=4k+1
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Graph: showing that diameter is greater than average pairwise distance
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
MHB Prove the minimum and maximum edges in a graph
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
MHB Finding a Minimal Vertex Cover & Max Sets for a Graph
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
MHB Show that HSC is NP-complete
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top