Intereting Posts

Find all integer solutions to $7595x + 1023y=124$
Uniqueness of prime ideals of $\mathbb F_p/(x^2)$
Prove $\int_0^1\frac{x^2-2\,x+2\ln(1+x)}{x^3\,\sqrt{1-x^2}}\mathrm dx=\frac{\pi^2}8-\frac12$
Prove that $\binom{m+n}{m}=\sum\limits_{i=0}^m \binom{m}{i}\binom{n}{i}$
Sum of numbers on chessboard.
Show $\lim\limits_{n\to\infty} \frac{2n^2-3}{3n^ 2+2n-1}=\frac23$ Using Formal Definition of Limit
Why does the Pythagorean Theorem have its simple form only in Euclidean geometry?
The convergence of a sequence of sets
Limit of algebraic function $\ \lim_{x\to\infty} \sqrt{x^5 – 3x^4 + 17} – x$
Variant of Cauchy Functional Equation
How to change the order of summation?
Strong Induction proofs done with Weak Induction
Why square units?
Proving $\mathbb{Q} = \{f(\sqrt{2}): f(x) \in \mathbb{Q}\} = \{x+y\sqrt{2}:x,y\in\mathbb{Q}\}$
Proof of properties of dual cone

I’m trying to solve the following question:

Let $G$ be graph on $n ≥ 4$ vertices with $2n − 2$ edges. Prove that $G$ has

two cycles of equal length.

I have reached the following observations:

- incidence matrix of a digraph with a self loop
- Graph of a matrix
- Graph Theory book with lots of Named Graphs/ Graph Families
- Describe all graphs without a path of length 3
- Could one be a friend of all?
- Planar graphs with $n \geq 2$ vertices have at least two vertices whose degree is at most 5

- If I try and prove this by induction, during the induction step I have a graph of n vertices and if I remove the minimal-degree vertex it’s easy to see that if it has 2 or less edges, then the resulting graph is a graph of n-1 vertices and at least 2(n-1)-2 edges, so by the induction assumption there are two cycles of equal length. However I still need to prove that if the minimal degree in the original n-vertices graph is larger than 2, then this means it is still possible to find two equal length cycles (it’s no longer possible to remove a vertex and keep the required amount of edges).
- If a graph has a minimal degree of 3, then it has a cycle with a chord – perhaps this could help me here, alongside with the induction idea?
- If the minimal degree is 3 I believe this means that there must be a cycle of length 4 (at least one). Maybe it’s possible to look at this cycle and do something with it (maybe removing it…?)

Any help would be appreciated as I am currently a bit stuck.

- Motivation for spectral graph theory.
- Is there is a way to construct a covering space of a wedge of two circles for a given normal subgroup
- In a graph, connectedness in graph sense and in topological sense
- Radius, diameter and center of graph
- Is Reliability Component a vertex?
- Maximum number of edges that a bipartite graph with $n,m$ vertices can have when it doesn't contain $4$-cycle
- The Adjacency Matrix of Symmetric Differences of any Subset of Faces has an Eigenvalue of $2$…?
- Count Eulerian cycles in $K_{n,2}$
- Girth and monochromatic copy of trees
- Symmetric difference of cycles

Consider a spanning tree of the graph (or a spanning forest, the argument works analogously). The longest path of any tree is at most $n-1$ steps. Then when we add edges to a tree, we join vertices which have a distance of $2 \le d \le n-1$ between them. There are $n-2$ such distances and we must add at least $2n-2 – (n-1) = n-1$ edges. Therefore by the pigeon-hole principle, one distance $d$ must be repeated. This means that the graph has two cycles of length $d+1$.

- Every preorder is a topological space
- What is the cone of the conic section?
- Hahn-Banach to extend to the Lebesgue Measure
- Which trigonometric identities involve trigonometric functions?
- Is there a measure on $\mathbb{N}$? (What is the chance that a random integer from $\mathbb{N}$ is even?)
- A conformal geodesic map must be a scaled isometry?
- The Relative Values of Two Modified Bessel Function of the First Kind
- Conditional probability independent of one variable
- Probability of Obtaining the Roots in a Quadratic Equation by Throwing a Die Three Times
- A puzzle about integrability
- Necessary condition for positive-semidefiniteness — is it sufficient?
- For integers $a$ and $b$, $ab=\text{lcm}(a,b)\cdot\text{hcf}(a,b)$
- Nonnegative linear functionals over $l^\infty$
- Why does Wolfram Alpha say the roots of a cubic involve square roots of negative numbers, when all three roots are real?
- Is $\int_{M_{n}(\mathbb{R})} e^{-A^{2}}d\mu$ a convergent integral?