# Tag Info

1

The word path is often used in two different contexts: A path graph is a graph consisting of a sequence of vertices such that two vertices are adjacent in the graph if and only if they are consecutive in the sequence. The notation $P_n$ is often used for a path graph of length $n$. This is what Bondy & Murty describe. A path in a graph is a subgraph of ...

0

Ahh, I think Bondy and Murty mean adjacent in the path if they are consecutive in the sequence, and non-adjacent otherwise. It's just their way of saying no vertex is repeated; if no vertex is repeated, then two vertices are adjacent in the sequence iff they are consecutive in the sequence. Conversely, if two vertices manage to be adjacent in a sequence ...

0

This is how I can prove this one, Let $f_i (V(C_n))$ be a homomorphism from $C_n$ to any graph $X$, then we claim that if $v_0, v_1, v_2,..., v_{n-1}, v_n$ are vertices in $V(C_n)$ then $f(v_0),f(v_1),f(v_2),...,f(v_{n-1}),f(v_n), f(v_0)$ is a walk of length $n$ given that $v_0, v_1, v_2,..., v_{n-1}, v_n, v_0$ is an n-cycle. Suppose our claim is false, ...

2

Tl;Dr: A graph is just an abstract idea, whereas a graph embedding is an actual physical instance of a graph that has to be drawn (or embedded) onto some surface. In order to understand what a graph embedding is, it helps to first define what a graph is. Definition: A graph is a set vertices and a set of edges connecting those vertices. In a way we ...

2

The number of vertices of degree $d$ is equal to the number of vertices of degree $4k-d$. Thus for all $d\ne2k$ the number of vertices with degree $d$ or $4k-d$ is even. Since there is an odd number of vertices, there must be at least one remaining vertex with $d=2k$.

0

An alternative would be to use Prufer sequences. (If you don't know what these are, I suggest you look them up, and how they can be used to prove Cayley's formula before reading the rest of this hint). Write $A$ for the largest independent set in the split graph, and $B$ for the vertex set of the largest clique. Consider the following algorithm for ...

0

Show that for every pair of vertices $x,y$ there are $k$ internally disjoint $x,y$-paths, then use Menger's theorem. Distinguish two cases. If $x$ and $y$ are in different graphs, say $x\in G_1-v_1$ and $y\in G_2-v_2$, use an $x,N(v_1)$-fan and an $y,N(v_2)$-fan and glue them together using the matching. If $x$ and $y$ are in the same graph, say $G_1$, ...

0

Hint 1: Take a complete graph $K_n$ and take another vertex $v$ and join it to arbitrarily many vertices in the $K_n$. Notice that if you contract any edge incident to $v$, then you get just the $K_n$. Hint 2: Recall or look up the deletion-contraction formula for counting spanning trees. Fix a vertex $v$ from the independent set side of your complete split ...

0

For (c): Each corner of the hypercube can be labeled with a $k$-bit number. The mouse starts at $000..0$, the cat at $111..1$. They start with $k$ bits different. At each step, they both change one bit. If they start with $d$ bits different, then after that step they have either $d-2$, $d$ or $d+2$ bits different. Work out the probabilities. It becomes a ...

2

Here's a cleaner version of the 56 crossing. The left and right wrap around.

1

The graph is not completely connected, because there are no connexions between the points 1, 3, 5, 6, 9 and the points 2, 4, 7, 8. The correction would be to create a connexion from one set to the other.

0

The important thing here is that you need to exploit the differences in definition between $H_{3,2k}$ and $H_{3,2k+1}$. Induction seems a good idea, indeed. The induction base is trivial, since $H_{3,4}$ and $H_{3,5}$ actually are wheels. Case 1: $n=2k+1$ ($k\geq 3$). $H_{3,2k}$ is 3-connected by the induction hypothesis. Note that $H_{3,2k}$ is $C_{2k}$ ...

2

Your conjecture is incorrect. It might help to review the definitions of Eulerian circuit and Hamilton cycles and then draw some examples to get clues for the necessary conditions. For example, let me tell you that $K_{2,4}$ is Eulerian but it is not Hamiltonian. Why? Well you can just find an Eulerian circuit by hand. But now try to find a Hamiltonian ...

5

Here we go: $$\huge\cdot\qquad\cdot$$ remember that $0$ is even. The circuit is the "empty circuit" Since the graph has no edges, we've already passed every edge if we don't even move :D

0

This can be solved via the well-ordering principle. Let path P be the longest path in graph G that starts at point A, which has the lowest degree of the graph. If A has degree higher than 2, then it will have some neighboring point W. If W was not on P, then A would have a neighbor that's not on P, and then P would not be the longest path, so unless A's ...

1

"My reasoning was that if K >= N, then we are guaranteed a connected graph." -- This is not true; consider the graph $K_{n/2} + K_{n/2}$, which is a disjoint union of two cliques. This graph has about $n^2/4$ edges, but is clearly not connected.

1

I think your solution of 10 is optimal. This is not the solution, but I'm sketching a proof which I hope to finish soon. Let's take a look at parts that the optimal solution might have. It goes without proof that each point is at least in a triangle in some optimal solution. It follows almost immediately that at least one quadrilateral consisting of two ...

1

Seeking a contradiction, assume $G$ is not bipartite. Then $G$ has a cycle of odd length; let $v_0, v_1, \ldots ,v_{k}$ be the vertices of the cycle, in their respective order. As some notation, let $N(v)$ denote the set of neighbors of $v$. Then if $|i - j| >2$ (when taken $\mod(k)$), then we must have $N(v_i) \cap N(v_j) = \emptyset$ by the ...

3

Suppose by way of contradiction that $G$ is not bipartite, let $C$ be an odd cycle of minimal length $l$. Every vertex outside of $C$ is adjacent to at most $2$ vertices of $C$. If a vertex is adjacent to at least three vertices we can find an odd cycle smaller than $C$, this would be a contradiction (try to prove this, it is a good exercise). So what is ...

1

HINT: This is pretty straightforward if you just pay attention to the definition of graph homomorphism. Let $C_n$ be an $n$-cycle with vertex set $V=\{v_0,\ldots,v_{n-1}\}$ and edges $\{v_k,v_{k+1}\}$ for $k=0,\ldots,n-2$, and the edge $\{v_{n-1},v_0\}$. Let $G=\langle U,E\rangle$ be any graph. A homomorphism from $C_n$ into $G$ is a map $f:V\to U$ such that ...

2

Let $A$ be the adjacency matrix of one graph $G$, and $B$ the adjacency matrix of another graph $H$ which is cospectral to $G$. Thus $\text{tr}(A^k)=\text{tr}(B^k)$ for all nonnegative integers $k$. Recall that the $(i,i)$-entry of $A^k$ is the number of walks of length $k$ starting and ending at vertex $i$. Similarly for $B$ of course. Without loss of ...

2

You're missing the requirement that the $K_p$ or $K_q$ must be completely red and blue, respectively. $R(2,4)$ must be larger than $2$ because if you color the single edge in $K_2$ blue, then the resulting graph does not contain a red $K_2$, and does not contain a blue $K_4$ either.

3

You can always prevent one of them by colouring all edges the same color. Therefore it must be (inclusive) or. This gives, for instance, $R(2,n)=n$, since if there are $n$ vertices, then either you have a $K_2$ of one color, or all edges are of the second color and you have $K_n$ in that color. I think maybe the important point you've missed here is that ...

3

I'm thinking I'm making a mistake somewhere, since I suspect this would have been the first thing anyone would have checked for a counter example: The Petersen Graph. It can be verified that every two adjacent edges lie on a common chordless 5-cycle, yet the removal of any edge leaves the independence number at $4=\alpha (P)$. So, the Petersen Graph is not ...

3

I found the article where this fact is shown. However, I can't access it in it's entirety without paying... Here it is It shows the first page, but everything else is kind of blurred out. It does not have the same layout as Ed Pegg's answer. I will try and edit this with a picture of the graph, but in the meantime, if maybe you have access to the above ...

0

First show that a directed acyclic graph (DAG) must have a sink. (This is pretty straightforward: if there’s no sink, there must be a cycle (why?).) Now you can prove by induction on the number of vertices that every DAG can be numerically labelled so that each parent has a smaller label than each of its children: if it’s true for every DAG on $n$ vertices, ...

0

Well, think carefully about what you mean by a vertex being "higher" than another. Clearly, a vertex that has no outgoing edges is the lowest. A vertex that only points to such vertices is only one step higher. On the other hand, if there is a vertex with a path to every other vertex, that is clearly as high as one could possibly get. To be explicit, here's ...

0

I'm running into 60 as well. I'd also like to see the 56.

1

I checked the 41-vertex d=4 k=3 graph by James Allwright and found that it has a four clique in its line graph. I also checked the linegraph with this program but after a day of computing it did not find a 4 coloring. After reading this paper I learned that this problem (whether the James graph is 4 or 5 edge colorable) can be nowadays solved exactly in a ...

1

It sounds like you are conflating the concepts of clique, maximal clique, and clique graph. A clique of a graph $G = (V, E)$ is a set $X \subseteq V$ such that every two vertices in $X$ are adjacent (connected by an edge.) A maximal clique of $G$ is a clique $X$ which is as big as possible (i.e. adding any vertex would violate the clique condition.) The ...

0

No, it is a clique graph because the (maximal) cliques of the original graph become vertices in the new graph, and they are adjacent if the corresponding cliques share a vertex. The maximal cliques in the original graph are all of size 3, so the four $3$-cycles of the first graph are represented by the four vertices in the new graph. Any two $3$-cycles of ...

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 ...

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 ...

0

Hint: Consider a graph G having one vertex, and no edges. Either the empty graph H=({}, {}) is an allowed answer, or you have to create a graph with no vertices, but an edge...

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

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 ...

0

Consider a square $ABCD$ with four edges, and toss in an extra (curved) edge from $A$ to $B$. Then every vertex has neighbors with degrees 2 and 3, but there's no pendant vertex. So clearly your proof will depend on some property of "graphs" that's at least somewhat subtle: must there be at most one edge between any two vertices? Even if you rule out that ...

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 use Python and the NetworkX package: https://networkx.github.io/ Granted, there's some learning to be done in using it, but it's very straight forward and richly featured. And of course using Python makes the automation part simple too. Take a look. I've used it in a board game setting (machine learning) and finance. From their website: Features ...

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 ...

0

I didn't use any of this matrix stuff. I just simply assumed every statement they made was a lie and for G I constructed the set {D,M'} where M' means M didn't do it. Then for m I have (M, D}. Continuing I have {D', G}, {M', m'}, and {J', G} and conclude that G is the one none of them said did do it therefore G did it.

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.

0

Number of vertices with degree k =$n_k$ Number of vertices with degree k+1 =$n_k$ Number of edges = e Number of vertices = n n=$n_k +n_{k+1}$ $k*n_k+(k+1)*n_{k+1} = 2e$ [sum of degrees of a graph= 2e] $k*n_k+k*n_{k+1}+n_{k+1} = 2e$ $k*(n_k+n_{k+1})+n_{k+1} = 2e$ $k*n +n_{k+1} =2e$ $n_{k+1} =2e-kn$ $n_k =n-n_{k+1}$ $n_k ... 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. 0 Let me give an answer in a different direction: Your problem is to find the terminal strongly connected components. The complexity of this problem is not bad for any sense of bad used in computer science, but I understand that you want the most efficient algorithm. Try to look into computer science literature, in particular search on graphs. I'm not an ... 0 This is an explanation of Thomas's comment, but too long for a comment: Each strongly connected component of the transition graph that has no exit edges supports a unique stationary distribution which is ergodic. On the other hand, every stationary distribution is supported on the union of such strongly connected components (transient components have no ... 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 ... 0 First we rule out the$k$. Since we know it belongs to$W$we can remove it from the graph. We also modify the cost of the neighbour of$k$in order to take into account the prize received from the edge with$k$. Thus the new cost of$i$is$v_i-x_{(k,i)}$. (Notice that if a cost is now negative we know that this vertex belongs to$W$hence we can repeat ... 0 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. 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 ...

Top 50 recent answers are included