Tag Info

Hot answers tagged

3

The problem has no solution. One of the statements It was M and It wasn't M must be true, so It wasn't D must be false. Therefore $D$ is guilty. But then both of $M$'s statements are true.


2

First we show that there is no Eulerian graceful polyhedral graph. Suppose a polyhedral graph can be created. For a polyhedral graph we need minimum degree 3. Since each vertex except the endpoints is even this means that for $n$ vertices we will need at least $2n-1$ edges. Even in the best case the last edge must go from $2n-1$ to 0, but this forces the ...


2

Yes, we pick a vertex, and make its connected component is one subgraph, and make the rest of the graph the other subgraph. (Note: the second subgraph might not be connected.) These two subgraphs are both vertex-disjoint (don't have a common vertex) and edge-disjoint (don't have a common edge). Yes for $n \geq 3$ vertices. If the vertices are ...


2

It's a consequence of the definition of matrix multiplication. The proof can be done by induction. For the induction step, write $M^k$ as $M^{k-1} \cdot M$, and then look at the $(i,j)$th entry, which is $$(M^{k-1}\cdot M)_{i,j} = \sum_{\ell=1}^n (M^{k-1})_{i,\ell} \cdot M_{\ell,j}.$$ For a given value of $\ell$, $(M^{k-1})_{i,\ell}$ is the number of ways ...


2

In the article they borrow the term from, the authors use $t$-disjoint to mean the edges are at distance at least $t$. Two edges in this particular graph $G$ that induce a subgraph of two disjoint edges are actually at distance at least $3$ (as opposed to $2$, as you might think), because the graph is bipartite.


1

The answers to the question you linked are not all correct. In particular, the answer relating to maximum flow computation is wrong. Let me first give you an example showing that this answer is wrong and then further readings stating correct algorithms for finding edge-disjoint trees in a graph. Consider the following graph: This graph obviously admits ...


1

I found this exposition of the Smallest Eigenvalues of a Graph Laplacian by Shriphani Palakodety to be readable and informative. The article begins with a discussion of eigenvectors for the smallest eigenvalue, which in the case of the graph Laplacian happens to be zero. The number of eigenvectors for this eigenvalue gives the connected components of the ...


1

If you know that simple, connected graphs with no loops or cycles (AKA trees) with $n$ vertices have $n-1$ edges, then by the Handshaking Lemma, you have $$\sum_{v\in V}\deg(v) = 2n-2.$$ If $n\geq 2$, then $\deg(v)\geq 1$ for every vertex $v$, but now notice that the equation can only be satisfied if at least two summands on the left are exactly $1$.


1

Let's define a superGraph to be simple, connected graph with no loops or cycles. This is because I don't want to have to repeat the phrase "simple, connected graph with no loops or cycles" over and over. Firstly, this claim isn't true for a superGraph with $0$ or $1$ vertices. It is pretty clearly true for the single possible graph with two vertices. ...


1

Let $u_1$ be a vertex, and assume that all the other vertices have degree greater than one. Since the graph is connected, there is a vertex $u_2$ that has degree $\geq2$ and is adjacent to $u_1$. Similarly, we find a vertex $u_3\neq u_1$ adjacent to $u_2$, and so on. Since the graph is finite, it happens that $u_i=u_j$, for some $i\neq j$. In other words, we ...


1

Of course, we assume that the graph has at least two vertices. Choose a vertex $v$ at random. For a general vertex, $w$, define $L_v(w)$ to be the length of a minimal path connecting $v$ to $w$ and let $N$ be a vertex for which this length is maximal. Then we claim that $N$ has degree $1$. To see this, suppose it were false. Then $N$ would have some ...


1

First handle the case that there are no edges (the truth in this case depends on exactly how you specify the problem; your first statement is ambiguous/incorrect; your second statement (in the comment) makes it untrue for these graphs, since there are no two neighbours of one vertex with the same degree, but there is no pendant vertex). Use following proof ...


1

Am my friend has said we must find the characteristic polynomial as the product of factors and solve an inductive sequence and we will be done.


1

Another way to think about: $\mathcal{K}^+[Y]$. Given a set $Y$ of vertices, $\mathcal{K}^+[Y]$ consists of all those vertices that are either on the boundary of $Y$ or on the boundary of a vertex in the boundary of $Y$. That is, start with $Y$ and then include all those vertices that are either parents of or adjacent (non-directedly) to any of the ...


1

No. Not in general. $E$ is a set of unordered pairs of $V$, so switching them can only be done when the vertices have degree 2 (so $G$ is some number of loops). You could of course make the vertices out of the edges. Then make edges in $H$ whenever the edges in $G$ share a vertex. But that means you'll get multiple edges in $H$ for every vertex in $G$. As ...


1

I think G must have said 'It was m' rather than 'It was M'. That's according to your matrix. According to J, it must either be m or M. But if it was m, then G is not lying in either of his statements. Then it must be M.


1

I have read and agree with Scott that there is no solution, but for a different reason. I do not use graph theory, either. Since there exists one and only one criminal, $G$'s "It was M" has to be a lie, (otherwise both D and M are criminals) which implies that neither D nor M is the criminal. However, since $m$ lies one and only once, either D or M is the ...


1

I would suggest 'Introduction to Graph Theory' by Douglas B. West.I love this book.Excellent book content.Great for beginners.



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