TITLE: How do we interpret $E=|\vec{p}|c$ in classical electromagnetism?
QUESTION [1 upvotes]: $$E=|\vec{p}|c$$
Can this relation be derived purely from electromagnetic theory?
I.e., is this a general statement about the EM field as whole and not just individual photons?
I.e.
$$\left(\frac{1}{2}\epsilon_{0}|\vec{E}|^2 + \frac{1}{2\mu_0} |\vec{B}|^2\right) dv \ = \ |\epsilon_{0}\vec{E}×\vec{B}| \ dv(c) $$
The energy within a volume $dv$, is equal to the momentum in volume $dv * c$.
I am fairly confident that this expression is not true.
The closest relation I can get is:
$$\vec{S} = \frac{\vec{p}}{c^2}$$
Which is a relation about the energy FLUX and momentum density, (multiply by c), and it fits the same form, but how would we interpret $\vec{S} c$, where the units are:
$$\frac{J}{ms} \ \ \ ?$$

REPLY [3 votes]: The closest relation I can get is

$\vec{S} = \frac{\vec{p}}{c^2}$

This looks backwards.
We can define the electromagnetic momentum density $\vec p$ as:
$$
\vec p \equiv \frac{\vec S}{c^2}\;.
$$
For an electromagnetic plane wave travelling in the $\hat z$ direction, we also have a relationship between the Poynting vector $\vec S$ and the energy density $u$:
$$
\vec S = uc\hat z\;.
$$
Using the above two equations we can write:
$$
u=pc
$$


TITLE: Choosing $N$ to prove a sequence is Cauchy
QUESTION [0 upvotes]: Let $\epsilon > 0$. Suppose $f:\mathbb{R}\to \mathbb{R}$ is a function. In an $\epsilon$-$N$ proof, would it be acceptable (or good practice) to say, "Choose $N$ such that $f(N)<\epsilon.$"?
Normally (if $g: \mathbb{R}\to \mathbb{R}$ is a function) I would say something along the lines of "Choose $N=g(\epsilon)$", and continue on with the standard $n>N\implies n>g(\epsilon)\ldots$
For example, suppose $a\in(0,1)$ and I needed to choose $N$ such that $a^n<\epsilon \space \space\space (\forall n>N)$, so in my proof would it suffice to say "Choose $N$ such that $a^N < \epsilon$. Then $n>N\implies a^n < \epsilon\ldots$"

REPLY [3 votes]: Doesn't work, I'm afraid. Consider the following fake proof that $\sin(x)$ converges to $0$ as $x \to \infty$:

Suppose $\varepsilon > 0$. Choose
  $$N = \begin{cases}\arcsin(\varepsilon) & \text{if } \varepsilon \le 1 \\ \pi/2 & \text{if } \varepsilon > 1. \end{cases}$$
  Then, always $\sin(N) \le \varepsilon$, hence (???)
  $$x > N \implies \sin(x) < \varepsilon.$$

In the specific case of the $a^n$ proof, it sort of works, because $n \mapsto a^n$ is both positive and decreasing, when $a \in (0, 1)$. So, if you know that $a^N < \varepsilon$ and $N < n$, then by definition of increasing, $a^N > a^n$, hence $a^n < \varepsilon$. It's also important that $a^n > 0$, so that $|a^n - 0| = a^n < \varepsilon$.
However, in order to reason in this way, it's important to prove that $n \mapsto a^n$ is indeed decreasing, and show that an $N$ exists such that $a^N < \varepsilon$.


TITLE: For what value of $n \in \Bbb N$ the function $f(x)=x^n$ is uniformly continuous in all of the set $\Bbb R$
QUESTION [2 upvotes]: For what value of $n \in \Bbb N$ the function $f(x)=x^n$ is uniformly continuous in all of the set $\Bbb R$_
I've been trying to work on this problem but I don't really know what to do.
Can you help me understand this problem?

REPLY [3 votes]: Hint: Suppose $n>1.$ Let $\delta > 0.$ Then by the mean value theorem,
$$(x+\delta)^n-x^n = nc^{n-1}\delta,$$
where $c\in (x,x+\delta).$


TITLE: General formula of fraction integral
QUESTION [2 upvotes]: Consider the sequences of integrals:
$\int \frac{x}{1+x} dx, \int \frac{x}{1+x^2}dx, \int \frac{x}{1+x^3}dx,\ldots,\int \frac{x}{1+x^n}dx$.
Question: What is the general formula of $\int \frac{x}{1+x^n} dx$  for $n>0$?

REPLY [2 votes]: It's not a complete answer, but too long for a comment. It gives the answer for $n=4m$, $m$ is positive integer. Denote $I_n:=\int\frac{x}{1+x^n}\,dx$.  If $x<0$ then substituting $x:=-z$ we can reduce the problem for $x>0$. So we calculate $I_{4m}:=\int\frac{x}{1+x^{4m}}\,dx$. Substitute $x:=\sqrt{z},\,z>0$. Then $I_{4m}=\frac{1}{2}\int\frac{1}{1+z^{2m}}\,dz$. The result of the integral is (Demidovich, Mathematical Analysis, problem 1925)
$$
-\frac{1}{2m}\sum_{k=1}^{m}\cos\frac{\pi(2k-1)}{2m}\ln\left(1-2x\cos\frac{2k-1}{2m}\pi+x^2 \right)$$
$$+\frac{1}{m}\sum_{k=1}^m\sin\frac{\pi(2k-1)}{2m}\arctan\frac{x-\cos\frac{2k-1}{2m}\pi}{\sin\frac{2k-1}{2m}\pi}.
$$


TITLE: eigenvalue decomposition using matlab
QUESTION [2 upvotes]: I would like to diagnolize a rank-1 matrix using the well known eigenvalue decomposition as
$\mathbf{U}^H\mathbf{A}\mathbf{U} = diag (M, 0,\cdots, 0)$, where $\mathbf{A}$ is a Hermitian matrix and $\mathbf{U}$ is a unitary matrix.
While if we use eig.m in matlab, the resulting $\mathbf{U}$ fails to satisfy the property of unitary matrix $\mathbf{U}^H\mathbf{U} = \mathbf{I}_{M}$ due to the unit round-off error and the use of \pi.
What should I do?
The code can be given:
    clc
    clear all
    close all

    c           = 340;
    j           = sqrt(-1);
    theta_s     = 0;
    theta_s     = theta_s*pi/180;

    M           = 6;
    delta       = 0.012;
    M_vector    = (0:M-1)';
    theta       = 0:0.1:360;
    theta       = theta*pi/180;

    f           = 4000;

    %% eigenvalue decomposition of matrix
    omega       = 2*pi*f;
    d           = exp(-j*omega*M_vector*delta/c);
    h_DS        = 1/M*d;
    A           = d*d';

    [U,D]       = eig(A);

REPLY [3 votes]: Due to round-off errors, MATLAB isn't recognizing that your matrix is Hermitian.  You can fix this easily by averaging A with its Hermitian transpose:
>> ishermitian(A)

ans =

  logical

   0

>> B=(A+A')/2;
>> ishermitian(B)

ans =

  logical

   1

Once you've done this, U'*U=I as expected.
>> [U,D]=eig(B);
>> U'*U

ans =

  Columns 1 through 4

   1.0000 + 0.0000i  -0.0000 + 0.0000i   0.0000 + 0.0000i  -0.0000 - 0.0000i
  -0.0000 - 0.0000i   1.0000 + 0.0000i  -0.0000 - 0.0000i  -0.0000 - 0.0000i
   0.0000 - 0.0000i  -0.0000 + 0.0000i   1.0000 + 0.0000i   0.0000 - 0.0000i
  -0.0000 + 0.0000i  -0.0000 + 0.0000i   0.0000 + 0.0000i   1.0000 + 0.0000i
   0.0000 - 0.0000i   0.0000 - 0.0000i   0.0000 - 0.0000i  -0.0000 + 0.0000i
  -0.0000 + 0.0000i  -0.0000 - 0.0000i   0.0000 - 0.0000i   0.0000 + 0.0000i

  Columns 5 through 6

   0.0000 + 0.0000i  -0.0000 - 0.0000i
   0.0000 + 0.0000i  -0.0000 + 0.0000i
   0.0000 + 0.0000i   0.0000 + 0.0000i
  -0.0000 - 0.0000i   0.0000 - 0.0000i
   1.0000 + 0.0000i   0.0000 + 0.0000i
   0.0000 - 0.0000i   1.0000 + 0.0000i


TITLE: Six counters are tossed. How many outcomes are possible if the six counters are distinguishable? Indistinguishable?
QUESTION [0 upvotes]: Counters are kind of like coins with two different colours on each side. By distinguishable I mean that each of the 6 counters has different colours. For instance, 1= blue and green, 2= red and black, 3= silver and golden, and so on..
So how many outcomes are possible if the counters are distinguishable.

REPLY [0 votes]: Take each counter one by one. Now each one of them has two possibilities irrespective of the outcomes of the other counters. In short each counter has results which are independent of the other counters.
So let's say if there was only one counter. Then the answer would simply be $2$. If there were two counters, for each outcome of the first, we have two of the second. Thereby giving us
$$N = 2*2 = 4$$
Extrapolating this philosophy for $6$ counters, we have
$$N = 2*2*2*2*2*2 = 2^6 = 64$$
So number of outcomes is $64$. Keep in mind that this is the total number of possibiliyies if you fix the order of flipping i.e. say that Blue/Green is flipped $1st$, Red/Black is flipped $2nd$ and so on so forth. If the order is not fixed either, you multiply this with $6!$ (number of permutations of counters), you get
$$N = 64*6! = 46080$$
If the counters are indistinguishable, this becomes a multiple coin toss problem with no permutations possible as coins are all same and total no of outcomes as
$$N = 64$$
I am also attaching a link of a basic coin toss guide
http://www.probabilityformula.org/coin-toss-probability.html


text:
\begin{document}

\maketitle

\begin{abstract}
Analogous to the characterisation of Brownian motion on a
Riemannian manifold as the development of Brownian motion on a
Euclidean space, we construct sub-Riemannian diffusions
on equinilpotentisable sub-Riemannian manifolds
by developing a canonical stochastic process arising as the lift
of Brownian motion to an associated model space. The notion of
stochastic development we introduce for equinilpotentisable
sub-Riemannian manifolds
uses Cartan connections, which take the place of the Levi--Civita
connection in Riemannian geometry.
We first derive a general expression
for the generator of the stochastic process which is the
stochastic development with respect to a Cartan connection of the
lift of Brownian motion to the model space.
We further provide a necessary and sufficient condition for the
existence of a Cartan connection which develops the canonical
stochastic process to the sub-Riemannian diffusion associated with
the sub-Laplacian defined with respect to the Popp volume. We
illustrate the construction of a suitable Cartan connection for free
sub-Riemannian structures with two generators and we discuss an
example where the condition is not satisfied.
\end{abstract}

\section{Introduction}
\label{sec:intro}
\input{introduction}

\section{Overview of Cartan geometry}
\label{sec:cartan_geom}
\input{overview}

\subsection{Cartan geometry on a sub-Riemannian manifold}
\label{sec:scartan}
\input{srcartan}

\section{Stochastic development in sub-Riemannian
  geometry}
\label{sec:develop}
\input{develop}

\section{Cartan connections for
sub-Riemannian diffusions}
\label{sec:cartan}
\input{examples}

\subsection{The three-dimensional contact case}
\label{sec:3d}
\input{3dcontact}

\subsection{Free sub-Riemannian structures with
  two generators}
\label{sec:ttfive}
\input{ttfive}

\bibliographystyle{siam}
\bibliography{references}

\end{document}

config: arxiv


TITLE: Deriving the Power Spectral Density of a Maximum Entropy Process
QUESTION [1 upvotes]: In Elements of Information Theory, Chapter 12, Section 6 Burg's Theorem is derived: Presented with the first $p$ values of the autocovariance function $R(k) = E[X_i X_{i+k}]$ a stochastic process maximizing the entropy rate is constructed. In (12.55) the power spectral density of that process is presented:
$$S(\lambda) = \frac{\sigma^2}{\lvert 1 + \sum_{k=1}^p \alpha_k \exp(-i k \lambda) \rvert^2}$$
Where $\{\alpha_i\}$ may be derived by the Yule-Walker equations. Since no derivation is presented and I couldn't find a suitable way to tackle this problem: Can someone either point me to a reference where this power spectral density is derived or give me a hint on how to get started?

REPLY [1 votes]: The derivation is rather lengthy, and is found in many textbooks. Here's an sketch:
$$S(\omega )=\sum_{k=-\infty}^\infty R_k \, e^{-i\omega k } \tag{1}$$
relates the spectral density of an stationary signal with its second order statistics. We assume $R(k)$ is fixed for $|k|\le m$, and we want to find $R(k)$ for $|k|> m$ so that the entropy $H$ is maximized.
Now, it's known that for a given (full) second order statistics, a Gaussian process maximizes the entropy. And for such a process the entropy can be expressed as:
$$ H =  \int \log S(\omega ) d\omega  \tag{2}$$
Because we want to maximize with respect to the free parameters, $R(k)$ for $|k|\ge m$, we derive with respect of them and set the derivative to zero:
$$\frac{d H}{d R(k)}= \int \frac{1}{S(\omega )} e^{-i\omega k}d\omega =0 \hspace{1cm} |k|\ge m\tag{3}$$
Taking the inverse Fourier transform we can write $S^{-1}$ as
$$S^{-1}(\omega )=\sum_{k=-m}^m C(k) e^{-i\omega k} \tag{4}$$
for some symmetric $C(k)$, or
$$ S(\omega )=\frac{1}{\sum_{k=-m}^m C(k) e^{-i\omega k}}$$
This can be factorized (Fejer-Riesz Lemma):
$$\sum_{k=-m}^m C(k) z^{-k}=\frac{A(z)A(z^{-1})}{\sigma^2} \tag{5}$$
which implies that $S(\omega )$ is the spectral density of an AR process.
In Cover's book an alternative derivation is presented (similar to this one). There, we first see that the Gaussian process maximizes entropy for a given second order statistic (like here), and afterwards we note that, if we consider the process as a Gaussian Markov process, then, among all such processes (again, restricting to the subset that fullill the restriction of the known $R(k)$) the one with the smallest order is the one that maximizes the entropy ( basically, because it's the one that has less "conditions" over the past). But a finite order AR process is a Markov process - and for given $R(k)$ we can find the corresponding AR coefficients (and hence $A(z)$) via the Yule Waler equations, and hence the resulting spectrum.


text:
\begin{document}
\newcommand{\QED}{\hfill \blacksquare}
\newcommand{\m}{\textnormal{mult}}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\renewcommand{\baselinestretch}{1.1}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{cla}[thm]{Claim}
\newtheorem{lm}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{example}[thm]{Example}

\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{alg}[thm]{Algorithm}

\newtheorem{rem}[thm]{Remark}

\title{\bf  An Analogue of the Gallai-Edmonds Structure Theorem for Nonzero Roots of the Matching Polynomial}
\author{
Cheng Yeaw Ku
\thanks{ Department of Mathematics, Caltech, Pasadena, CA 91125, USA. E-mail: cyk@caltech.edu.} \and William Chen \thanks{ MSC 176, Caltech, Pasadena, CA 91125, USA. E-mail:
chenw@caltech.edu} }

\maketitle

\begin{abstract}\noindent
Godsil observed the simple fact that the multiplicity of 0 as a root of the matching polynomial of a graph coincides with the classical notion of deficiency. From this fact he asked to what extent classical results in matching theory generalize, replacing ``deficiency" with multiplicity of $\theta$ as a root of the matching polynomial. We prove an analogue of the Stability Lemma for any given root, which describes how the matching structure of a graph changes upon deletion of a single vertex. An analogue of Gallai's Lemma follows. Together these two results imply an analogue of the Gallai-Edmonds Structure Theorem. Consequently, the matching polynomial of a vertex transitive graph has simple roots.
\end{abstract}

\section{Introduction}
A {\em matching} of a graph $G$ is a set of pairwise non-adjacent edges of $G$. Classical matching theory is mostly concerned with the maximum size $\nu(G)$ of a matching in $G$, known as the {\it matching number}. Another important quantity is the number of vertices $\mbox{def}(G)$ missed by a maximum matching, known as the {\it deficiency}. They are related by the formula $\mbox{def}(G)=|V(G)|-2\nu(G)$.

Recall that for a graph $G$ on $n$ vertices, the {\it matching
polynomial} $\mu(G,x)$ of $G$ is given by
\[ \mu(G,x)=\sum_{k \ge 0} (-1)^{k}p(G,k)x^{n-2k}, \]
where $p(G,k)$ is the number of matchings with $k$ edges in $G$. Let $\m(\theta, G)$ denote the multiplicity
of $\theta$ as a root of $\mu(G,x)$. Godsil observed that $\m(0,G)=\mbox{def}(G)$ and obtained several results in \cite{G} generalizing classical results involving $\mbox{def}(G)$ to analogous $\m(\theta,G)$ versions. The present paper is concerned with such a generalization for the celebrated Gallai-Edmonds Structure Theorem.

The following definition introduced by Godsil in \cite{G} (who adapted it from \cite{N}) is useful in stating the theorem. It assigns to each vertex a ``sign''---minus, zero, or plus---based on how the multiplicity of a root of the matching polynomial changes when that vertex is deleted. This definition is fundamental to the work here.
\begin{dfn}\label{def}
Let $\theta$ be a root of $\mu(G,x)$. For any vertex $u\in V(G)$,
\begin{itemize}
\item $u$ is $\theta$-{\em essential} if $\m(\theta, G
\setminus u)<\m(\theta, G)$,

\item $u$ is $\theta$-{\em neutral} if $\m(\theta, G
\setminus u)=\m(\theta, G)$,

\item $u$ is $\theta$-{\em positive} if $\m(\theta, G
\setminus u)>\m(\theta, G)$.
\end{itemize}
\end{dfn}
\begin{rem}A vertex is $0$-essential if and only if it is missed by
some maximum matching of $G$. There are no $0$-neutral vertices.
\end{rem}
\begin{rem}If $\m(\theta, G)=0$ then there are no $\theta$-essential
vertices since the multiplicity of a root cannot be negative.
Nevertheless, it still makes sense to talk about $\theta$-neutral
and $\theta$-positive vertices when $\m(\theta, G)=0$.
\end{rem}
We will often omit the $\theta$- prefix from these terms if it is clear from context.

A further classification of vertices plays an important role in describing the Gallai-Edmonds Structure Theorem:
\begin{dfn}Let $\theta$ be a root of $\mu(G,x)$. For any vertex $u\in V(G)$, $u$ is $\theta$-{\em special} if it is
not $\theta$-essential but has a neighbor that is $\theta$-essential.
\end{dfn}

The Gallai-Edmonds Structure Theorem describes a certain canonical decomposition of $V(G)$. Its statement
essentially consists of two lemmas, the Stability Lemma and Gallai's Lemma. For more
information, see \cite[Section 3.2]{LP}. The main results of the present paper are the following analogues for the Stability Lemma and Gallai's Lemma for any root of the matching polynomial. Their classical counterparts are simply the case $\theta=0$.
\begin{thm}[Stability Lemma]\label{main}
\noindent Let $G$ be a graph with $\theta$ a root of
$\mu(G,x)$, $u$ a $\theta$-special vertex in
$G$ and $v$ a vertex of $G$ different from $u$. Then
\begin{itemize}
\item $v$ is $\theta$-essential in $G$ if and only if $v$ is $\theta$-essential in $G\setminus u$,

\item $v$ is $\theta$-neutral in $G$ if and only if $v$ is $\theta$-neutral in $G\setminus u$,

\item $v$ is $\theta$-positive in $G$ if and only if $v$ is $\theta$-positive in $G\setminus u$.
\end{itemize}
\end{thm}
\begin{rem}
This result is slightly different from the classical Stability Lemma because it includes neutral vertices. Recall that there are no $0$-neutral vertices.
\end{rem}

It follows from Theorem \ref{main} that after deleting the special vertices, the essential vertices remain essential. Furthermore, they are not joined to the other non-essential vertices. Therefore it is interesting to study graphs whose vertices are all $\theta$-essential. These graphs are called {\it $\theta$-primitive}, and generalize the factor-critical graphs. Gallai's Lemma is a fundamental result about the structure of these graphs when $\theta=0$. We prove this for any root $\theta$.
\begin{thm}[Gallai's Lemma]\label{main2}
\noindent If every vertex of $G$ is $\theta$-essential, then $\m(\theta,G)=1$.
\end{thm}

The following corollary is immediate since every vertex of a vertex transitive graph is $\theta$-essential, see \cite{G}.
\begin{cor}
The matching polynomial of a vertex transitive graph has simple roots.
\end{cor}

This answers a question of Godsil in \cite[Problem 6.1]{G1} and disproves a conjecture of Mohar \cite{M}: for every integer $r$ there exists a vertex transitive graph $G$ whose matching polynomial has a root of multiplicity at least $r$.

\section{Basic properties}
In this section, we collect some basic identities and properties of the matching polynomial proved in \cite{G0} and \cite{G}. If $u\in V(G)$, then $G \setminus u$ is the graph obtained from $G$ by deleting vertex $u$ and the edges of $G$ incident to $u$. We also denote the graph $(G \setminus u) \setminus v$ by $G \setminus uv$. If $e\in E(G)$, the graph $G-e$ is the graph obtained from $G$ by deleting the edge $e$. If $f\not\in E(G)$ is a pair of distinct vertices, then $G+f$ is the graph obtained by adding $f$ as an edge to $G$.

The matching polynomial satisfies the following basic identities.
\begin{prop}
Let $G$ and $H$ be graphs, with matching polynomials $\mu(G,x)$ and $\mu(H,x)$, respectively. Then
\begin{itemize}
\item[\textnormal{(a)}] $\mu(G \cup H,x) = \mu(G,x)\mu(H,x)$,
\item[\textnormal{(b)}] $\mu(G,x)=\mu(G - e, x)-\mu(G
\setminus uv,x)$ where $e=\{u,v\}$ is an edge of $G$,
\item[\textnormal{(c)}] $\mu(G,x) = x\mu(G \setminus u,x)-\sum_{v
\sim u} \mu(G \setminus uv,x)$ for any vertex $u$ of $G$.
\end{itemize}
\label{identity}
\end{prop}
Proposition \ref{identity}(a) says that the matching polynomial can be considered separately for each connected component of a disconnected graph. We will use Proposition \ref{identity}(b) frequently, and it is especially applicable to the results of Section 3.

Another useful result due to Godsil guarantees the existence of a $\theta$-essential vertex in a graph whose matching polynomial has $\theta$ as a root. This implies that every vertex of a vertex transitive graph is $\theta$-essential for any root $\theta$.
\begin{lm}\label{essential}
Any $G$ with $\m(\theta, G)>0$ must have at
least one $\theta$-essential vertex.
\end{lm}

Godsil \cite{G0} showed that the roots of $G\setminus u$ interlace those of $G$. This puts a limitation on how much the multiplicity of a given root of the matching polynomial can change upon deleting a vertex. In this paper, as in Godsil's, we often refer to this phenomenon as ``interlacing.''
\begin{prop}
Let $G$ be a graph, $u \in V(G)$ a vertex of $G$. Then $\m(\theta,G\setminus u)$ differs from $\m(\theta,G)$ by at most one.
\end{prop}
The notions of $\theta$-essential, neutral, and positive introduced in Definition \ref{def} should be viewed under this useful proposition.

The next result says that a $\theta$-special vertex must be $\theta$-positive and has significant consequences for the Gallai-Edmonds decomposition.
\begin{lm}\label{no-neutral-essential}
A $\theta$-neutral vertex cannot be joined to a $\theta$-essential
vertex.
\end{lm}

If $P$ is a path in $G$, then $G \setminus P$ denotes the graph
obtained from $G$ be deleting the vertices of $P$ and all the edges
incident to these vertices.

One of its important corollaries implies that if $u$ and $v$ are adjacent vertices of $G$, then $u$ cannot be $\theta$-essential in $G\setminus v$ if $v$ is $\theta$-essential in $G$. More generally,
\begin{cor}\label{interlacing-path}
For any root $\theta$ of $\mu(G,x)$ and a path $P$ in $G$,
\[ \m(\theta, G \setminus P) \ge \m(\theta, G)-1. \]
\end{cor}
As in Godsil's paper \cite{G}, we say that $P$ is {\it $\theta$-essential} if $\m(\theta, G \setminus P)
= \m(\theta, G)-1$. This connection is further motivated by the following.
\begin{lm}\label{no-path}
The end vertices of a $\theta$-essential path are themselves $\theta$-essential.
\end{lm}

Using these tools, Godsil proved a result very similar to the Stability Lemma.
\begin{prop}[Theorem 4.2, \cite{G}]\label{delete-positive}
Let $\theta$ be a root of $\mu(G,x)$
and let $u$ be a $\theta$-positive vertex in $G$. Then
\begin{itemize}
\item[\textnormal{(a)}] if $v$ is $\theta$-essential in $G$ then it
is $\theta$-essential in $G \setminus u$,
\item[\textnormal{(b)}] if $v$ is $\theta$-positive in $G$ then it
is $\theta$-essential or $\theta$-positive in $G \setminus u$,
\item[\textnormal{(c)}] if $u$ is $\theta$-neutral in $G$ then it is
$\theta$-essential or $\theta$-neutral in $G \setminus u$.
\end{itemize}
\end{prop}
\begin{rem}
The Stability Lemma says that the sign of a vertex does not change upon deleting a special vertex. Proposition \ref{delete-positive} investigates how the sign changes when deleting a positive vertex.
\end{rem}

It is not difficult to formulate similar results for neutral vertices using the same techniques from Godsil's proof in \cite{G} of Proposition \ref{delete-positive}. In many ways, positive and neutral vertices behave similarly. Since the proof is almost identical to that of Godsil, we omit it here.

\begin{prop}\label{delete-neutral}
Let $\theta$ be a root of $\mu(G,x)$
and let $u$ be a $\theta$-neutral vertex in $G$. Then

\noindent (a) if $v$ is $\theta$-essential in $G$ then it is
$\theta$-essential in $G \setminus u$,

\noindent (b) if $v$ is $\theta$-positive in $G$ then it is
$\theta$-positive or $\theta$-neutral in $G \setminus u$,

\noindent (c) if $v$ is $\theta$-neutral in $G$ then it is
$\theta$-neutral or $\theta$-positive in $G \setminus u$.
\end{prop}

The result for essential vertices follows easily from the previous two.

\begin{prop}\label{delete-essential}
Let $\theta$ be a root of $\mu(G,x)$
and let $u$ be a $\theta$-essential vertex in $G$.

\noindent (a) if $v$ is $\theta$-positive in $G$ then it is
$\theta$-positive in $G \setminus u$,

\noindent (b) if $v$ is $\theta$-neutral in $G$ then it is
$\theta$-neutral in $G \setminus u$.

\noindent In particular, if $v$ is $\theta$-essential in $G
\setminus u$ where $u$ is $\theta$-essential in $G$, then $v$ is
$\theta$-essential in $G$.
\end{prop}
\begin{proof} Suppose $v$ is $\theta$-positive in $G$. Then, by Proposition
\ref{delete-positive}, $\m(\theta, G \setminus uv)=\m(\theta, G
\setminus vu)=\m(\theta, G)$, so $v$ is $\theta$-positive in $G \setminus u$.
Now, suppose $v$ is $\theta$-neutral in $G$. By Proposition
\ref{delete-neutral}, $\m(\theta, G \setminus uv) = \m(\theta, G
\setminus vu) = \m(\theta, G)-1$ so that $v$ is neutral in $G \setminus u$.
\end{proof}
The proof of Proposition \ref{delete-essential} is based on the trivial observation that the order in which vertices are deleted is immaterial, a technique that is used extensively in this paper.
\begin{rem}
Propositions \ref{delete-positive}, \ref{delete-neutral}, and \ref{delete-essential} are best possible in the sense that they place the most severe restrictions on the sign of the vertices of $G\setminus u$ in each case. That is, only the possibilities explicitly excluded do not occur.
\end{rem}

\section{Edge manipulations}

Let $G^*$ be the graph obtained by adding an edge to $G$, say $f=\{u,v\}$. Since $G^*\setminus u=G\setminus u$ and $G^*\setminus v=G\setminus v$, the signs of $u$ and $v$ must be the same relative to each other. The actual signs are determined by the multiplicity of $G^*$. The same argument works when deleting edges.

First we consider what happens to the multiplicity of $\theta$ upon adding an edge.

\begin{lm}\label{add-essential-positive}
Let $u$ be a $\theta$-positive vertex in $G$. Then for any nonadjacent vertex $v\ne u$,
$$\m(\theta, G+f) = \m(\theta, G),$$
where $f=\{u,v\} \not \in E(G)$.
Therefore $u$ is $\theta$-positive in $G+f$ and $v$ has the same sign in $G+f$ as it did in $G$.
\end{lm}
\begin{proof} Let $k=\m(\theta, G)$ and $G^*=G+f$. Recall the statement of Proposition \ref{identity}(b), which in this case states that
\begin{equation}
\mu(G^*,x)=\mu(G,x)-\mu(G^*\setminus uv,x).
\label{eq1}
\end{equation}
Since $u$ is positive, $\m(\theta,G^*\setminus uv)=\m(\theta,G\setminus uv)\geq k$, and (\ref{eq1}) gives that $\m(\theta,G^*)\geq k$.

If $v$ is essential in $G$, $\m(\theta,G^*\setminus v)=\m(\theta,G\setminus v)=k-1$, so by interlacing $\m(\theta, G^*)\leq k$.

If $v$ is neutral in $G$, $\m(\theta,G^*\setminus v)=k$ so by interlacing $\m(\theta, G^*)\leq k+1$. If $\m(\theta, G^*)=k+1$ then $u$ is neutral and $v$ is essential in $G^*$, contradicting Lemma \ref{no-neutral-essential}. It follows that $\m(\theta, G^*)\leq k$.

If $v$ is positive in $G$, then by Proposition \ref{delete-positive}, either $\m(\theta,G^*\setminus uv)=k+2$ or $\m(\theta,G^*\setminus uv)=k$. In the first case, $\m(\theta, G^*) \le k$ by (\ref{eq1}) and we are done. In the second case, $v$ is essential in $G^*\setminus u$. But this is impossible, because if $u, v$ are both neutral in $G^*$ then this contradicts Proposition \ref{delete-neutral}, and if $u,v$ are both essential in  $G^*$ then this contradicts Corollary \ref{interlacing-path}.
\end{proof}

\begin{lm}\label{add-neutral-essential}
Let $u$ be a $\theta$-neutral vertex and $v \ne u$ be a nonadjacent $\theta$-essential
vertex in $G$. Then $\m(\theta, G+f)= \m(\theta, G)-1$, where $f=\{u,v\} \not \in E(G)$. Therefore $u$ is $\theta$-positive and $v$
is $\theta$-neutral in $G+f$.
\end{lm}
\begin{proof} Let $k=\m(\theta, G)$ and $G^*=G+f$. By Proposition \ref{delete-neutral}, $\m(\theta, G^*\setminus uv)=\m(\theta, G \setminus uv)=k-1$. By (\ref{eq1}) and interlacing, it follows that $\m(\theta, G^*)=k-1$.
\end{proof}

For the other cases the situation is not as clean. Of those cases, the following lemma will be useful for our purposes, although similar results can be proven for other sign combinations.
\begin{lm}\label{add-essential-essential-I}
Let $u, v$ be nonadjacent $\theta$-essential vertices in $G$ such that $\m(\theta, G \setminus uv)
\ge \m(\theta, G)-1$. Then, either
\begin{itemize}
\item[$\bullet$] $\m(\theta, G+f)=\m(\theta, G)-1$ and both $u$ and $v$ are $\theta$-neutral in $G+f$, or
\item[$\bullet$] $\m(\theta, G+f)=\m(\theta, G)$ and both $u$ and $v$ are $\theta$-essential in $G+f$.
\end{itemize}
\end{lm}
\begin{proof} Let $k=\m(\theta, G)$ and $G^*=G+f$. By (\ref{eq1}), $\m(\theta, G^*) \ge k-1$
using the assumption that $\m(\theta, G \setminus uv) \ge k-1$. Since
$\m(\theta, G^* \setminus u)=\m(\theta, G \setminus u)=k-1$, by interlacing it follows that
$\m(\theta, G^*) \le k$.
\end{proof}

Now we consider what happens to
the multiplicity of $\theta$ when we
delete an edge $e=\{u,v\}$ from $G$.

\begin{lm}\label{delete-edge}
Let $u$ be a $\theta$-special vertex in $G$, adjacent to a
$\theta$-essential vertex $v$. Let $e=\{u,v\} \in E(G)$. Then $\m(\theta, G-e) = \m(\theta, G)$, therefore $u$ remains
$\theta$-positive and $v$ remains $\theta$-essential in $G-e$.
\end{lm}
\begin{proof}
Let $k=\m(\theta, G)$ and $G'=G-e$. Notice that $\m(\theta,G'\setminus u)=\m(\theta,G\setminus u)=k+1$ and $\m(\theta,G'\setminus v)=\m(\theta,G\setminus v)=k-1$. By interlacing it follows that $\m(\theta,G)=k$.
\end{proof}

\begin{lm}\label{delete-neutral-positive}
Let $u$ be a $\theta$-positive vertex in $G$, adjacent to a $\theta$-neutral
vertex $v$. Let $e=\{u,v\} \in E(G)$. Then, either
\begin{itemize}
\item[$\bullet$] $\m(\theta, G-e) = \m(\theta, G)+1$, $u$ is $\theta$-neutral and $v$ is $\theta$-essential in $G-e$, or
\item[$\bullet$] $\m(\theta, G-e) = \m(\theta, G)$, $u$ is $\theta$-positive and $v$ is $\theta$-neutral in $G-e$.
\end{itemize}
\end{lm}

\begin{proof}Let $k=\m(\theta, G)$ and $G'=G-e$. By Proposition
\ref{delete-positive}, $\m(\theta, G \setminus uv) \ge k$.
Applying \ref{identity}(b), we have
$\m(\theta, G') \ge k$. As $\m(\theta, G' \setminus v) = \m(\theta,
G \setminus v) = k$, it follows that $\m(\theta, G') \le k+1$ by
interlacing.
\end{proof}

\section{Three lemmas}

In this section, we study the effect of deleting an edge
incident to a $\theta$-special vertex. This will yield three lemmas used in the proof of Theorem \ref{main} by induction. We first consider the case
when a $\theta$-special vertex has two $\theta$-essential neighbors.

\begin{lm}\label{bac-not-essential}
Let $u$ be a $\theta$-special vertex in $G$ adjacent to two
$\theta$-essential vertices $v$ and $w$ in $G$, and let $e=\{u,v\} \in E(G)$. Suppose that the path $vuw$ is not $\theta$-essential in $G$. Then $u$ is $\theta$-special in
$G-e$, $w$ is $\theta$-essential in $G-e$ and
$\m(\theta, G-e)=\m(\theta, G)$.
\end{lm}

\begin{proof}Let $G'=G-e$ and $k=\m(\theta, G)$. By Lemma \ref{delete-edge}, it follows that
$\m(\theta, G')=k$, $u$ is positive in $G'$ and $v$ is
essential in $G'$, so it is enough to show that $w$ remains an
essential neighbor of $u$ in $G'$.

Notice by Proposition \ref{delete-essential} $u$ is positive in $G\setminus w$. Also, $v$ cannot be essential in $G\setminus w$, otherwise by Proposition \ref{delete-positive} the path $vuw$ is essential in $G$. So $v$ is either neutral or positive in $G\setminus w$.

If $v$ is neutral in $G\setminus w$, then by Lemma \ref{delete-neutral-positive} it follows that either $\m(\theta,G'\setminus w)=k$ or $\m(\theta,G'\setminus w)=k-1$. In the latter case we are done, so we show that the first case is not possible. In that case, $u$ is neutral and $v$ is essential in $G'\setminus w$, so by Proposition \ref{delete-neutral} $\m(\theta,G\setminus vuw)=\m(\theta,G'\setminus wuv)=k-1$, contradicting the assumption that the path $vuw$ is not essential in $G$.

If $v$ is positive in $G\setminus w$, then $u$ must be positive in $G\setminus wv$, otherwise by Proposition \ref{delete-positive} $u$ is essential in $G\setminus wv$ so $vuw$ is an essential path in $G$. Therefore, $\m(\theta,G\setminus vuw)=k+1$. Now consider the sign of $w$ in $G'$. The vertex $w$ cannot be neutral in $G'$, otherwise $\m(\theta,G\setminus wv)=\m(\theta, G'\setminus wv)=k-1$ by Proposition \ref{delete-neutral} so $\m(\theta,G\setminus vuw)\ne k+1$ by interlacing. If $w$ is essential in $G'$ we are done, so we may assume $w$ is positive in $G'$.

Since $\m(\theta, G' \setminus
wu)=\m(\theta, G \setminus uw)=k$, $u$ is
essential in $G' \setminus w$. By Proposition \ref{delete-positive}, $v$ is also
essential in $G' \setminus w$. Since $\m(\theta, G' \setminus w)=k+1$, applying Lemma \ref{add-essential-essential-I} to
$G' \setminus w$ yields $\m(\theta, G \setminus w)=\m(\theta, (G' \setminus w)+e) \ge k$, contradicting that $w$ is essential in $G$.
\end{proof}

Next, we consider the situation in which a $\theta$-special vertex
$u$ has a $\theta$-essential neighbor $v$ and a $\theta$-neutral
neighbor $w$. It turns out that $u$ is still $\theta$-special after deleting the edge $\{u,w\}$.

\begin{lm}\label{special-neutral}
Let $u$ be a $\theta$-special vertex and $v$ be a $\theta$-essential
neighbor of $u$ in $G$. Suppose $w$ is a $\theta$-neutral neighbor
of $u$ in $G$, $e=\{u,w\} \in E(G)$. Then $u$ is $\theta$-special in $G-e$, $v$
is $\theta$-essential in $G-e$ and $\m(\theta, G-e)=\m(\theta, G)$.
\end{lm}

\begin{proof} Let $G'=G-e$ and $k=\m(\theta, G)$. By Lemma
\ref{delete-neutral-positive}, either $\m(\theta, G')=k+1$ or $\m(\theta, G')=k$.

If $\m(\theta, G')=k+1$, then $u$ is
neutral and $w$ is essential in $G'$. Since $\m(\theta, G' \setminus u) = \m(\theta, G \setminus u) =
k+1$ and $\m(\theta, G' \setminus uv)=\m(\theta, G \setminus uv) =
k$, $v$ must be essential in $G' \setminus u$. As $u$ is
neutral in $G'$, by Proposition \ref{delete-neutral}, $v$
must be essential in $G'$, contradicting Lemma
\ref{no-neutral-essential}.

If $\m(\theta, G')=k$, then $u$ is positive and $w$ is neutral in $G'$. By Proposition \ref{delete-neutral} $\m(\theta, G' \setminus wv) = \m(\theta, G \setminus vw)=k-1$. So $v$ is
essential in $G' \setminus w$. As $w$ is neutral
in $G'$, by Proposition \ref{delete-neutral} again, $v$ is
essential in $G'$. So $u$ is special in $G'$ since
it is positive in $G'$ and is joined to $v$ in $G'$.
\end{proof}

A similar result holds when $u$ is adjacent to a $\theta$-positive vertex.

\begin{lm}\label{special-positive}
Let $u$ be a $\theta$-special vertex in $G$ and $v$ a
$\theta$-essential neighbor of $u$ in $G$. Suppose $w$ is a $\theta$-positive neighbor of $u$
in $G$, $e=\{u,w\}$. Then $u$ is $\theta$-special in $G-e$, $v$ is
$\theta$-essential in $G-e$ and $\m(\theta, G-e)=\m(\theta,G)$.
\end{lm}

\begin{proof}
Let $G'=G-e$ and $k=\m(\theta, G)$.

If $u$ were neutral in $G'$, then $\m(\theta,
G')=k+1$. By Lemma \ref{no-neutral-essential}, $v$ cannot be
essential in $G'$. So, by Proposition \ref{delete-neutral},
we have $\m(\theta, G' \setminus uv)
\ge k+1$, contradicting that $\m(\theta, G' \setminus uv)=\m(\theta, G \setminus uv)=k$. So $u$ cannot be neutral in $G'$. If $u$ were essential in $G'$,
then $\m(\theta,
G')=k+2$. But $\m(\theta,G'\setminus uv)=\m(\theta,G\setminus uv)=k$, contradicting Corollary \ref{interlacing-path}.

Therefore $u$ is positive in $G'$, and $\m(\theta, G')=k$. Using Lemma \ref{identity} (b),
\begin{eqnarray}\mu(G
\setminus v, x)=\mu(G' \setminus v, x)-\mu(G \setminus vuw, x) \label{e1}.
\end{eqnarray}
If $v$ is not essential in $G'$ then $\m(\theta, G' \setminus v) \ge k$,
so by Lemma \ref{no-path}, the multiplicity of $\theta$ on the right hand side of (\ref{e1})
is always at least $k$, contradicting the fact that $\m(\theta, G
\setminus v)=k-1$ on the left hand side. Therefore, $v$ is
essential in $G'$ and so $u$ is special in $G'$.
\end{proof}
\section{The Gallai-Edmonds Structure Theorem}

We are now ready to prove Theorem \ref{main}. In view of Proposition
\ref{delete-positive}, it remains to show that for any $\theta$-special vertex $u$, $v$ is
$\theta$-essential in $G \setminus u$ only if $v$ is $\theta$-essential
in $G$.

It is easy to show that $v$ cannot be $\theta$-neutral in $G$.
\begin{prop}\label{not-neutral}
Suppose $u$ is $\theta$-special in $G$ and $v$ is $\theta$-essential in $G \setminus u$. Then $v$ cannot be $\theta$-neutral in $G$.
\end{prop}
\begin{proof}
Suppose $v$ is neutral in $G$ and $k=\m(\theta,G)$. Let $w$ be an essential vertex adjacent to $u$ in $G$. Since $\m(\theta,G\setminus uv)=k$, $u$ is neutral in $G\setminus v$. But $w$ is essential in $G\setminus v$, contradicting Lemma \ref{no-neutral-essential}.
\end{proof}

\begin{proof}[Proof of Theorem \ref{main}]
The proof is by induction on the degree of $u$. Let $w_1$ be an essential vertex witnessing that $u$ is special, and let $e=\{u,w_1\} \in E(G)$. We may also assume that $\theta \not = 0$.

\noindent{\bf Base Case:} Notice that $w_1$ cannot be the only neighbor of $u$, otherwise by Lemma \ref{delete-edge}, $u$ is positive in $G-e$, a contradiction since $u$ is isolated in $G-e$. Suppose $\deg(u)=2$. Let $w_2$ be the second neighbor of $u$. Then by Lemmas \ref{bac-not-essential}, \ref{special-neutral}, and \ref{special-positive}, it follows that $w_2$ is essential and the path $w_1uw_2$ is essential in $G$, otherwise by deleting an edge $u$ would be a special vertex with only one neighbor.

For a contradiction, we now assume, in view of Proposition \ref{not-neutral}, that $v$ is positive in
$G$. We first prove the following claims. Let $G'=G - e$. Note that $\m(\theta, G')=k$ by Lemma \ref{delete-edge}.

\noindent {\bf Claim 1.}~~$v$ is positive in $G'$.

Let $G^{*}=G+f$ where $f=\{v,u\} \not \in E(G)$. Since $G^{*} \setminus u =
G \setminus u$ and $G^{*} \setminus v = G \setminus v$, $u$ and $v$
must be both essential or both positive or both
neutral in $G^{*}$. Suppose $u$ and $v$ are both
essential or both neutral in $G^{*}$. Then
$\m(\theta, G^{*}) \ge k+1$ since $\m(\theta, G^{*} \setminus u) =
\m(\theta, G \setminus u) =k+1$. By the interlacing property of a
path, $\m(\theta, G^{*} \setminus w_1uw_2) \ge k$, contradicting the
fact that $\m(\theta, G^{*} \setminus w_1uw_2) = \m(\theta, G \setminus
w_1uw_2)=k-1$. Therefore, $u$ and $v$ are both positive in
$G^{*}$ and $\m(\theta, G^{*})=k$.

If $v$ is neutral in $G'$ then $\m(\theta, G' \setminus vw_1)
= k-1$ by Proposition \ref{delete-neutral}. But $\m(\theta, G'
\setminus vw_1)=\m(\theta, G \setminus vw_1)=k$ by Proposition
\ref{delete-positive} since $v$ is positive and $w_1$ is
essential in $G$. So $v$ is either positive or
essential in $G'$.

Suppose $v$ is essential in $G'$. By Proposition
\ref{delete-positive}, $w_2$ is essential in $G \setminus u =
G' \setminus u$. Let $H$ denote the graph which is the union of $G'
\setminus u$ and the isolated vertex $u$. By Lemma
\ref{add-neutral-essential}, $w_2$ is neutral in $G'=H+\{u,w_{2}\}$, $u$ is
positive in $G'$ and $\m(\theta, G')=k$. Now, deleting $v$
first from $G'$ followed by deleting $w_2$ and $u$, we deduce that
$\m(\theta, G' \setminus vw_2u)=k-1$ using Proposition
\ref{delete-essential} and Proposition \ref{delete-neutral}. Since
$G^{*} \setminus vuw_2 = G' \setminus vuw_2$, we deduce that $vuw_2$ is
essential in $G^{*}$, whence $v$ is essential in
$G^{*}$ by Lemma \ref{no-path}. This contradicts the conclusion of
the first paragraph following Claim 1.

Hence, $v$ is positive in $G'$, proving Claim 1.

\noindent {\bf Claim 2.}~~$\m(\theta, G' \setminus vw_2)=k$.

Since $\m(\theta, G' \setminus vu)=\m(\theta, G \setminus uv)=k$
(recall that $v$ is essential in $G \setminus u$ by our
hypothesis), it follows immediately from Claim 1 that $u$ is
essential in $G' \setminus v$. Then, being adjacent to $u$,
$w_{2}$ is either essential or positive in $G'
\setminus v$ (Lemma \ref{no-neutral-essential}). If $w_{2}$ is
positive in $G' \setminus v$, then $u$ remains
essential in $(G' \setminus v)-e'$ where $e'=uw_2 \in E(G'
\setminus v)$ by Lemma \ref{delete-edge}. However, as an isolated
vertex in $(G' \setminus v) - e'$, $u$ has to be neutral
(since $\theta \not =0$) in $(G' \setminus v) - e'$, contradicting
the preceding sentence. So $w_{2}$ is essential in $G'
\setminus v$ and $\m(\theta, G' \setminus vw_2)=k$, thus proving Claim
2.

Finally, recall that $w_1$ is essential in $G'$ (Lemma
\ref{delete-edge}) and $v$ is positive in $G'$ (Claim 1).
Also, by Lemma \ref{add-neutral-essential}, $w_2$ is
neutral in $G'=H+\{u,w_{2}\}$. By Claim 2, $v$ is neutral in $G' \setminus w_{2}$. Clearly, as $\theta \not = 0$, the isolated vertex
$u$ is neutral in $G' \setminus vw_2$. Subsequently, using
Proposition \ref{delete-neutral}, by deleting $w_{2}$ from $G'$ followed by deleting $v$ from $G'\setminus w_{2}$, we deduce that $\m(\theta, G \setminus
vw_2uw_1) = \m(\theta, (G' \setminus w_2v) \setminus uw_1)=k-1$. On the
other hand, by interlacing (Corollary \ref{interlacing-path}),
$\m(\theta, G \setminus vw_1uw_2)= \m(\theta, (G \setminus v) \setminus
w_1uw_2) \ge \m(\theta, G \setminus v)-1 = k$ since we assume $v$ is positive in $G$, contradicting the preceding sentence. This establishes the theorem when $\deg(u)=2$.

We may now assume that $\deg(u) \ge 3$.

\noindent{\bf Inductive Step:} Let $w_1$ be an essential neighbor of $u$ witnessing that $u$ is special. If $w_2\neq w_1$ is adjacent to $u$ and $w_1uw_2$ is not a essential path, let $e_2=\{u,w_2\}$ and $G_2=G- e_2$. By the three Lemmas \ref{bac-not-essential}, \ref{special-neutral}, and \ref{special-positive}, $u$ is still special in $G_{2}$ and $\m(\theta, G_2)=\m(\theta, G)$. By the induction hypothesis, $v$ is essential in $\m(\theta, G_{2})$, so $\m(\theta, G_2\setminus v)=\m(\theta,G)-1$. Since $u$ is still positive in $G_2\setminus v$, by Lemma \ref{add-essential-positive} $\m(\theta, G\setminus v)=\m(\theta, (G_2\setminus v)+e_2)=\m(\theta,G)-1$, so $v$ is essential in $G$.

If for every vertex $w\neq w_1$ adjacent to $u$ the path $w_1uw$ is an essential path, let $w_2,w_3$ be two such vertices. Let $e_3=\{u,w_3\}$ and $G_3=G- e_3$. By Lemma \ref{delete-edge}, $\m(\theta,G_3)=\m(\theta,G)$ and $u$ is positive in $G_3$. Since $w_1uw_2$ is still an essential path in $G_3$, $w_1,w_2$ are essential in $G_{3}$ (Lemma \ref{no-path}), so $u$ is special in $G_{3}$. Now the proof follows as before: by the induction hypothesis, $v$ is essential in $G_3$, so $\m(\theta, G_3\setminus v)=\m(\theta,G)-1$. Since $u$ is still positive in $G_3\setminus v$, by Lemma \ref{add-essential-positive} $\m(\theta, G\setminus v)=\m(\theta, (G_2\setminus v)+e_3)=\m(\theta,G)-1$, so $v$ is essential in $G$.
\end{proof}

With the Stability Lemma in hand, we can state a weak version of the Gallai-Edmonds Structure Theorem. Denote by $A(G)$ the set of all $\theta$-special vertices of $G$ for some root $\theta$ of $\mu(G,x)$. Deleting the $\theta$-special vertices one by one, the Stability Lemma says that the $\theta$-essential vertices of $G\setminus A(G)$ form $\theta$-primitive components and, by Lemma \ref{essential}, the non-essential vertices form components not having $\theta$ as a root. Let $D(G)$ be the set of $\theta$-essential vertices of $G$ and $C(G)=V(G)\setminus (A(G)\cup D(G))$. The partition of $V(G)$ into $A(G)$, $C(G)$, and $D(G)$ is called the {\it Gallai-Edmonds decomposition}. It will be useful to keep the above in mind for the proof of Theorem \ref{main2}, which states that if every vertex of a graph $G$ is $\theta$-essential, then $\m(\theta,G)=1$.

\begin{proof}[Proof of Theorem \ref{main2}]
Set $k=\m(\theta,G)$. Assume for a contradiction that $\m(\theta, G \setminus v)=k-1>0$. Using the notation above, let $D=D(G\setminus v)$,  $A=A(G\setminus v)$, and $C=C(G\setminus v)$. Let $w\in A$. Starting from $w$, we now delete the vertices of $A$ from $G$ one by one. The multiplicity of $\theta$ in $G\setminus A$ is at most $k+|A|-2$, since $w$ is essential in $G$ and by interlacing deleting the other $|A|-1$ vertices increases the multiplicity by at most $|A|-1$.

Abusing notation, let $D$ be the subgraph of $G$ induced by $D$. Since $\m(\theta,G\setminus v)=k-1$, it follows from the Stability Lemma applied to $G \setminus v$ that $\m(\theta,D)=k-1+|A|$.  By Corollary \ref{interlacing-path}, $v$ is not adjacent to any vertices of $D$. Since $D$ are components of $G\setminus A$, by Proposition \ref{identity}(a), $\m(\theta,G\setminus A)$ is at least $\m(\theta,D)$, a contradiction.
\end{proof}

The result just proved gives more structure to the Gallai-Edmonds decomposition. For example, $\m(\theta,G)$ is the difference of $|A(G)|$ from the number of components induced by $D(G)$. For the case $\theta=0$, the powerful tools offered by Theorems \ref{main} and \ref{main2} are known as the Gallai-Edmonds Structure Theorem.


TITLE: Elastic potential
QUESTION [0 upvotes]: I have a doubt:
elastic potential energy is given by: $U=\frac{k}{2}x^2+K$
but does elastic potential exist? (for example: potential gravitational energy is given by $U=mgz+K$ and gravitational potential is given by $V=-U$)
($K$ is the constant of integration)

REPLY [1 votes]: Elastic type potential exists for the system in equilibrium. If you have a potential function $U(x)$, you can always write down its Taylor series around the equilibrium point $x_0$ as
$$U(x) = U(x_0) + U'(x_0)(x-x_0) + \frac{1}{2}U''(x_0)(x-x_0)^2 + ... $$
Since the system is in equilibrium at $x_0$, so the net force $F=-U'(x_0)=0$. If we only consider the local region around the equilibrium point and set $x_0=0$, then the result is
$$U(x) = \frac{1}{2}k x^2 + K $$
where $K=U(x_0)$ and $k=U''(x_0)$.
You might argue that it is only approximation, but in reality, we always focus on a small region and wont consider large $x$ because the system is not isolated anymore. Also mathematically this expression becomes true if you take the limit of $x\to 0$.
Spring push objects away when compressed and pull them together when stretched. Therefore, it creates a potential energy function with a minimum and so the elastic potential for Hookes law follows. Note that when you stretch the spring heavily, it starts to distort and the potential is not quadratic anymore as we discussed above.