Tag Info

8

Consider the graph with 1000 vertices where vertex $i$ is adjacent to $j$ iff $|i-j|$ is neither prime nor square. There are at most $2*(168+31)=398$ vertices which are not adjacent to any point, so each vertex has degree at least $999-398=601>1000/2$. Since each vertex has degree greater than half the size of the graph, it's a well-known theorem that ...

6

Let $G$ be a graph with the stated properties. Let's label one of the vertices $0$. It has three neighbors, so let's label them $1$, $2$, and $3$ in some order. Then we will label the other two neighbors of $1$ with $11$ and $12$ in some order, and so on. So now as much of the graph as we know about looks like this. Since $G$ has ten vertices, we have ...

5

The set $\Gamma$ has infinitely many elements. For example, any closed path of the form $C_1^m C_2^n$ with $m,n \ne 0$ is primitive. On the other hand, the closed path $C_1 C_2 C_1 C_2$ is not primitive, since it can be written as $(C_1 C_2)^2$. The weird thing about this infinite product is that it's equal to the reciprocal of a finite polynomial. So let's ...

5

Second part is not correct. Intuition: since trees are not 2 vertex connected, you can fix one vertex and construct the tree such that vertices on the left has to pass through this vertex to reach vertices on the right. Then, construct 2 such trees and you will get counterexample for second part. Counterexample: $𝑇_1=𝑣_1−𝑣_2−𝑣_3−𝑣_4−𝑣_5−𝑣_6−𝑣_7−𝑣_8−... 4 Both you and the solution are wrong. Just saying that$\deg^-(c) \ne \deg^-(g)$doesn't mean anything, because$c$doesn't have to be paired with$g$. An isomorphism of these two directed graphs would be a function $$\phi : \{a, b, c, d\} \to \{e, f, g, h\}$$ that preserves directed edges. Checking that$\deg^-(c) \ne \deg^-(g)$tells you that we cannot have ... 4 Those two cycles are made up of the same set of edges. You're traversing them in a different order, but the edge$c - b$in$a - c - b - d - a$is the same as the edge$b - c$in$b - c - a - d - b$. 4 In a$d$-regular graph, the all-ones vector is an eigenvector with eigenvalue$d$; this is$\lambda_1$, the largest eigenvalue. If the graph is not connected at all, then the eigenspace of$d$is multidimensional: any vector which is constant on connected components of the graph is also an eigenvector. Now suppose$G$is connected, but very sparsely: for ... 4 It is Theorem$7$in this PDF, and there is a proof of the result for the integer lattice and an indication of how to modify it for the rational lattice here. 4 Initially the question said "$2$-regular graphs". It was changed to labelled graphs after I had written this answer. So, the first part of the answer addresses unlabelled graphs, and the second part (after the EDIT) explains why I think it would be hard to extend this to labelled graphs. A finite$2$-regular graph is a disjoint union of cycles, ... 4 Yes, and what's more, for any dominating set$W$of$G$, there is a spanning tree$T$for which$W$is also a dominating set. Begin choosing$T$by going through all vertices$v \notin W$, and adding an edge from$v$to some vertex$w \in W \cap N(v)$. This gives us a star forest in which$W$is a dominating set. It can be extended to a spanning tree however ... 4 Assume$G$is a graph and$X$is a set such that every vertex is in$X$or adjacent to a vertex in$X$. We prove there is a spanning tree$T$of$G$such that every vertex is in$X$or adjacent to a vertex in$X$. For each vertex$v$not in$X$we add exactly one edge from$v$to$X$that is in$G$. After doing this the graph has no cycles, because it is ... 4 Yes, your network model is completely correct! Now you can try to calculate the maximum Flow through the network and if it equals the number of clients, it is possible to give every customer at least one of the items on his list. 4 Since you are considering a simple graph$\sum_{i=1}^n{\lambda_i}=\mathrm{tr}(A)=0$, and therefore$\lambda_1 = -\sum_{i=2}^n{\lambda_i}$. Now use this,$\mathrm{tr}(A^{2}) = 2e$and Cauchy-Schwarz inequality to get $$\lambda_1^2=\left(-\sum_{i=2}^n{\lambda_i}\right)^2\leq (n-1)\sum_{i=2}^n\lambda_i^2=(n-1)(2e-\lambda_1^2).$$ 3 The technical term for what you're asking about is the query complexity of a graph property. Query complexity is exactly the number of entries of the adjacency matrix we must look at to determine if the graph has the property we want or not. The worst possible query complexity is$\binom n2 = \frac{n(n-1)}{2}$: the number of pairs of vertices to ask a query ... 3 You can also construct it: Start with$1$and keep adding$6$i.e$1,7,13$until you hit$997$then go back to$3$and keep adding$6$until you get to$999$and go back to$5$repeat until$995$then go back to$2$repeat until$998$and go back to$4$repeat until$1000$and go back to$6$repeat until$996$and you're finished. The difference between ... 3 For every$v$, we can consider summing$d(v)\choose 2$as counting$d(v)\choose 2$pairs of$p,q\in N(v)$, where there exist edges$(p,v),(q,v)$. We show that these pair$(p,q)$s cannot coincide. If$(p,q)$appears twice when we consider node$v_1$and$v_2$,$p- v_1-q-v_2-p$is a$4$-cycle. The total number of such pairs is$|V| \choose 2. 3 Ok, so, with the help of an article found and provide by @dbal, I could formulate the following: \begin{alignat*}{2} & \text{maximize: } &\sum_{i=1}^n \sum_{j=1}^n p_ix_{ij} - \sum_{i=1}^n \sum_{j=1}^n c_{ij}x_{ij}& &\\ & \text{subject to: } & \sum_{j=2}^n x_{1j} = 1 \tag1\\ & & \sum_{j=1}^n x_{ij} \leq ... 3 We are not assuming that. We haved(A,L) = h_A$by definition: we picked$L$to be as far as possible from$A$. We have inequalities$d(B,A) \le h_B$and$d(B,L) \le h_B$because$h_B$is the maximum possible distance from$B$, and$d(B,A), d(B,L)$are distances from$B$. Even if$A$or$L$happen to be much close to$B$than that, the inequality still ... 3 To be clear, let me write in bold the random variables. We are generating at random the edge set$\mathbf E_{n,p}$, giving us a single random graph$\mathbf G_{n,p}$. For any graph$G$with$m$edges,$\Pr[\mathbf G_{n,p} = G] = p^m (1-p)^{N-m}$. The graph property$\mathscr P$is a set of graphs. We have $$\Pr[\mathbf G_{n,p} \in \mathscr P] = \sum_{G \... 3 Your graph is the complete bipartite graph K_{r, r}. 3 Yes, linear complexes are the same things as graphs. (Simple graphs, if you must, though I think it's more common to say "graph" and "multigraph" than "simple graph" and "graph".) But Zykov is writing to us from an alien universe (namely, the year 1949) which does not yet have a well-developed notion of graphs. These ... 3 I wrote a little python script to find all the simple paths in the graph from U to Q. It found 21 such paths. Here's the script: from collections import defaultdict adjacent = defaultdict(str) adjacent['q'] = 'rsx' adjacent['r'] = 'qst' adjacent['s']= 'qrw' adjacent['t']= 'ruv' adjacent['u']= 'ty' adjacent['v']= 'twy' adjacent['w']= 'svx' adjacent['x'... 3 If you define T(v) to be the image of the path from v to v_0, either it is the case that T(v') = T(v) \cup j, or else it is the case that T(v) = T(v') \cup j. In this case, yes: we could replace T(v) \cup T(v') \cup j by T(v) \cup j, or by T(v') \cup j, or by T(v) \cup T(v'). We would have to prove that this property holds for paths in a ... 3 We can construct a recurrence for these numbers. Using combinatorial classes we have the following class \mathcal{Q} of sets of undirected cycles of length at least three:$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{Q} = \textsc{SET}( \textsc{DHD}_{=3}(\mathcal{Z}) + \textsc{DHD}_{=4}(\mathcal{Z}) + \textsc{DHD}_{=5}(\... 3 Set up the standard incidence matrix, with columns as professors and rows as students. The entry is 1 if the professor recommends the student, and 0 otherwise. We're after the minimum number of students. Let there be$s$of them. If there are students that are recommended by 0 or 1 professor, we can remove them from the list and reduce$s$while not ... 3 In some uses, the value of the adjacency matrix is the number of parallel edges connecting the nodes. 3 I believe that what you are looking for are the algorithms "Color-Constant-Degree-Graph" and "6-Color-Rooted-Tree" in this paper. The 6 coloring algorithm uses a local algorithm to color the nodes of a graph by having nodes process their color based on their neighbors colors, synchronously. It does this in$O(log^*n)$time. In case you ... 3 Just to answer the easy question: For$n=5$,$K_5 - e$is$5$-universal. Any$5$-vertex planar graph can be triangulated, extending it to a$5$-vertex planar graph with$9$edges, which can only be$K_5 - e$. And since$K_5-e$has$5$vertices itself, every graph which contains all$5$-vertex planar graphs contains$K_5-e$. For$n>5$, there are multiple ... 3 Euler path is only possible if$0$or$2$nodes have odd degree, all other nodes need to have even degree - so that you can enter the node and exit the node on different edges (except the start and end point). Your graph has$6$nodes all of odd degree, that's why you can't find any Euler path. In general if there exists Euler paths you can get all of them ... 2 The resolvent method for determining Galois groups works over any field – not just$\mathbb Q$– and is enough to solve this question. To illustrate how consider coordinate values$a$and$b$in the following unit-distance embedding of$F_{56}A$with$D_{14}$symmetry:$a$and$b$satisfy$\$a^{4} \left(16 t^{4} + 16 t^{2}\right) - 64 a^{3} t^{3} + a^{2} \...

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