# Tag Info

4

If you delete the three middle vertices in the central row, the graph splits into four connected components. Therefore the graph does not have a Hamiltonian cycle.

3

The easiest way to prove that a Graph is Hamiltonian, by just finding any Hamiltonian path. Proving the inverse is not that easy. The only way I know is to somehow argue logically that if you first choose one edge then you can't choose a specific other edge which will somehow give a contradiction. You can try argue using degrees of nodes as well. However, ...

2

I think you are forgetting that the walks counted by the powers of the adjacency matrix can come and go through the same edge (because it is a walk, not a path). Simple example: \begin{align*} A &=\left[\begin{array}[cc] 00 & 1 \\ 1 & 0 \end{array}\right] \\ A^2&=\left[\begin{array}[cc] 01 & 0 \\ 0 & 1 \end{array}\right] \end{align*} ...

1

Actually, you will never have to remove an edge. For example, if your graph has $n$ vertices, you can number the vertices from $1$ to $n$ and then orient each edge to point to its higher numbered endpoint. This results in a DAG.

1

Let $V_1,...,V_m\subset V(G(n,p))=:V$ be all the possible choices of $\varepsilon n$ vertices of $G(n,p)$, that is, $|V_i|=\varepsilon n$ and $m={n\choose \varepsilon n}$. And we define the event $A_i=\{e(G[V_i,V\setminus V_i])= 0\}$, where $e(G[V_i,V\setminus V_i])$ count the number of edges between $V_i$ and $V\setminus V_i$ in $G(n,p)$. Then, we want to ...

1

Welcome to MSE! How many walks of length $0$ are there from $v$ to $v$? Only one, right? Just... don't move. How many walks of length $1$? Again, there's only one. You have to take the self loop from $v$ to $v$. How many walks of length $2$? Well, now there's two options. We can either go around the self loop twice, or we can go to $w$ and back. More ...

Only top voted, non community-wiki answers of a minimum length are eligible