# Tag Info

0

When you have two cut-sets $(S_1,T_1)$ and $(S_2,T_2)$ in a problem, you can often get a better picture of them by drawing a picture. Put all elements of $T_1\cap T_2$ in "Quadrant I", all elements of $S_1\cap T_2$ in "Quadrant II", all elements in $S_1\cap S_2$ in "Quadrant III", and all elements of $T_1\cap S_2$ in "Quadrant IV": ...

0

We have that $\Delta(G) = 1$ and that $G$ is regular, so $G$ is $1$-regular, meaning that $d(v) = 1$ for all $v \in V$. But: $$\sum_{v\in V} d(v) = 2 |E| \implies \sum_{v \in V} 1 = 2|E| \implies |V| = 2|E|$$ This shows that $|V|$ is even. Moreover, we know that no two edges in $G$ can share a common vertex because this implies the existence of a vertex ...

1

NP-Completeness deals with decision problems. So if you have the problem: INSTANCE: Let $G$ be a graph and let $x \leq |G|$ be an integer. DECISION: Does $G$ contain a subgraph isomorphic to $K_{x}$? This is NP-Complete. The optimization variant (finding the largest $x$) is NP-Hard.

0

Suppose $k_{l}(s,t,G) < p_{l}(s,t,G)$. Let $S$ be an arbitrary set of vertices such that $|S| = k_{l}(s,t,G)$ and consider $G - S$. Notice that each vertex in $S$ can only remove at most one of the vertex disjoint $(s,t)$-paths of length $l$. This is because the $(s,t)$-paths are vertex disjoint, so a vertex in $S$ belongs to either one path and the ...

0

Answer is no. Let $G$ be a graph such that $\bar{G}$ is the graph in the picture. It is clear from the picture that $\chi(\bar{G})=2$. We will properly color $\bar{G}$ using the colors red and blue. Let $V_{red}=\{a,b,c\},V_{blue}=\{1,2,3\}$ be the set of red and blue vertices respectively. The matching which you describe in formula (1) in your question can ...

1

Lagrange is not wellsuited for the discrete nature of the problem. Any bipartite subgraph of $K_n$ with $p$ and $q$ vertices can be extended to $K_{p,q}$, having $pq$ edges. If $n$ is even then $$pq=\frac14((p+q)^2-(p-q)^2)\le \frac14(n^2-0)$$ with equality if both $p+q=n$ and $p-q=0$, i.e., $p=q=\frac n2$. If $n$ is odd, we cannot have $p+q=n$ and ...

1

Your graphs do not all have the same unordered degree sequences. I count G1 : $[1, 1, 2, 2, 3, 3, 4]$ G2 : $[1, 1, 2, 3, 3, 3, 3]$ G3 : $[1, 1, 2, 3, 3, 3, 3]$ G4 : $[1, 1, 2, 2, 3, 3, 4]$ There are all sorts of other things you can look at to rule out isomorphism. For example, all the graphs have two vertices of degree one. What is the distance ...

0

$G_1$ and $G_4$ are isomorphic and $G_2$ and $G_3$ are isomorphic. Each graph has two vertices of degree 1. Look at where their edges join the rest of the graph. If you redraw each graph for maximum symmetry--i.e. reshape the triangle and quadrilateral in each to be an equilateral triangle and square, let's say, and then orient the edges involving the ...

1

Recall that the mothers of all non-planar graphs are $K_5$ and $K_{3,3}$. In what follows we need only that $K_5$ is not planar. If $G$ has no edges then all repeated strong products of $G$ with itself have no edges either, hence are planar. So assume $G$ contains at least one edge. Then $G\boxtimes G$ contains a $K_4$ and $G\boxtimes G\boxtimes G$ a ...

0

Take rock-paper-scissors, for example. More precisely: $*\colon \{0,1,2\}\times\{0,1,2\} \to \{0,1,2\}$ given by multiplication table $$\begin{array}{c | c c c} & 0 & 1 & 2\\ \hline 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 2\\ 2 & 0 & 2 & 2 \end{array}$$ which is obviously commutative, but not associative: $$(0*1)*2 = ... 0 Certainly it is possible to define the discrete topology on any set. If you like that your topology has applications, then you need more interesting examples. I am aware of some examples but they define a topology not only on the set of edges but on the set of vertices and edges. If the points of your topological space are the vertices and the edges then ... 1 Take any Lie algebra over a field of characteristic 2, where the Lie bracket is not associative (in particular, is not 2-step nilpotent). Then [x,y]=[y,x] for all x,y, but [x,[y,z]]\neq [[x.y],z]. An example is the 3-dimensional simple Witt algebra over characteristic 2, with basis (x,y,h) and brackets [x,y]=h,[h,x]=x and [h,y]=y. If you ... 1 Take for instance f(x,y)=2x+2y on \mathbb{N}. Then f(x,f(y,z))=2x+4y+4z and f(f(x,y),z)=4x+4y+2z. Another example is f(x,y)=2^{x +y} on \mathbb{N}. Then f(x,f(y,z))=2^{x + 2^{y + z}} and f(f(x,y),z) = 2^{2^{x + y} +z}. 0 Stronger - a graph with n vertices where deg(x)+deg(y) \ge n-1 for all non-adjacent vertices x,y has a Hamiltonian Path. Add a vertex v_0 to the graph, and connect v_0 with all vertices in the graph G. This makes a new graph G'. Apply Ore's Theorem on G' - since deg(x)+deg(y) \ge n+1 = |G'| for all non-adjacent vertices x,y, we have a ... 2 The grid graph is the Cartesian product of two copies of the path P_n. The eigenvalues of the Laplacian of the Cartesian product of two graphs are the sum of the eigenvalues of the Laplacians of the graphs. So the second largest eigenvalue of your grid is the sum of the largest and second largest eigenvalues of the Laplacian of the path P_n. Hence your ... 0 Here is a hint for the edge separator: write K_n = (V,E), where V denotes the set of vertices and E the set of edges. Now suppose that the removal of some edge set F \subseteq E leaves the graph disconnected, then we can choose a partition V = A \cup B of the vertices (with A \cap B = \varnothing, A \neq \varnothing and B \neq \varnothing) so ... 3 I'm not sure how much value I'm adding here, but perhaps this example will be interesting to kids of the modern age. Suppose we have the following two graphs of equal size: Graph 1: A group of youths with Facebook accounts. Some pairs of people in the group are friends on Facebook, some are not. Graph 2: A room full of pre-programmed old-school paging ... 0 Those are (more or less) the Ramsey numbers. 1 Well, there are two key observations: L_K=N I-J, where I is the identity matrix and J is the all-1-matrix. L_G * J=0 for any graph G, because each entry of the product is the sum of all entries of some row of L_G, which of course is zero. Now your formula follows. 1 Well, suppose your graph has diameter at least 3. Then there are two vertices x, y at distance at least 3. Take a shortest path between x and y. What can you say about this path ? 0 The following tree decomposition for the subgraph that is the subject of question 1 has width 4, thus establishing that as an upper limit on the treewidth for the subgraph. The remaining issue for question 1 is whether there is a tree decomposition with width 3 (below which one can most certainly not go). And question 2 is still open. X_1 = {F, Z, X, ... 1 To stick with your notation: (a,d)\ \{a,d\} (d,f)\ \{a,d,f\} (a,b)\ \{a,b,d,f\} (b,e)\ \{a,b,d,e,f\} (c,e)\ \{a,b,c,d,e,f\} (e,g)\ \{a,b,c,d,e,f,g\} Making the total cost 5+6+7+7+5+9=39. You went wrong in the third step, where you added (f,e) instead of (a,b). NB: Draw it yourself, check that you understand each step and verify that ... 1 If you first draw the complete tree from the matrix then using Prim's algorithm you just add the egde with the lowest value to the minimum spanning tree and continue doing so until all vertices are connected to the minimum spanning tree (of course you should'nt add any edge if it doesn't add another vertice to the tree). I personally think that it is a lot ... 1 Pick an arbitrary point in the graph. It's connected to at least \frac{n-1}{2} other vertices. Hence, the connected component of the graph containing our point has at least \frac{n+1}{2} points in it. This is more than half of the points in the graph, and so we're done, since if every connected component has more than half the points in it, there can't ... 0 Think about the termination condition. To generate a boy-optimal matching one runs the Gale-Shapley algorithm with the boys making proposals. It's easy to see that the algorithm terminates as soon as every girl has received a proposal (single girls are obliged to accept any proposal and, once every girl has received a proposal, no single boys remain). In ... 1 You can't! The graph with two vertices, both of which are of degree 5 (so connected 5 times to each other), is planar. The graph with one vertex of degree 6 (so it has three loops) is also planar. You need to add the constraint that the graph is "simple" before you can prove this statement. 0 You can find the proof in these lecture notes. 0 Your relation seems to be equivalent to a == b when a and b are on some cycle. This is an equivalence relation (assuming we're allowed cycles of length 1), and the required decomposition is into its equivalence classes. I've never seen this relation employed, but I don't know much :). 2 Edge contractions are not really so much algebraic graph theory as general graph theory. The subject is closely related to the subject of graph minors. Reinhard Diestel's book Graph Theory contains an entire chapter devoted to the famous graph minor theorem, including an outline of the proof. (The entire proof was published in a series of 20 papers.) The ... 1 To show that one of the statements is not true it suffices to give an example for which the statement is false. In the following example graphs the DFS is always started at node s and the orientation of the edges indicates the search direction. Edges that are not oriented are not traversed during the search. For statements 1. and 3. consider the following ... 1 Yes, it is just max(k,k') (assuming the two graphs do not share other vertices, otherwise the merge does not make sense). Let T_1,T_2 be the two trees corresponding to tree decompositions of the two graphs and let B_1,B_2 be bags of T_1,T_2 containing v,v' respectively. Then a tree decomposition for the merged graph is obtained by simply adding an ... 1 By "Eulerian graph", I take it you mean a graph that has an Euler circuit, that is, a walk that uses each edge exactly once and returns to the vertex where it started. What if your graph has a vertex of odd degree? If the walk starts there, once you leave the vertex, there are an even number of edges left to use. In order to use all the edges, when you ... 2 I mean that my proof is correct. 0 The Prim algorithm (https://en.wikipedia.org/wiki/Prim%27s_algorithm) is precisely based on this property of minimum spanning trees. The Proof of Correctness in Section 3 explains it quite well. 1 Every connected grapgh G is Eulerian grapg iff for every vertex v\in V_G, deg(v) is even. Suppose G is not connected, because for every v\in V_g, deg(v)=p, therefore every componnet of G has at least p+1 vertecis, and that means V_G>2p+1 which leads to contradiction, so G is connected. Also \sum_{v\in V_G}deg(v)=p(2p+1)=2E, therefore ... 0 This would be an example of an adjacency matrix A of a graph that is not simple. Each entry A_{ij} in the matrix corresponds to the number of edges between vertices i and j. For example, there are 5 edges between a and d, since A_{a,d}=5. If A_{ij} is a blank entry, then there are no edges between vertices i and j. From this, it should ... 0 In loose terms, two graphs G and H are said to be isomorphic if there is a way to "draw" the graph G to look like H. For example, consider the claw graph K_{1,3} and the path P_4 with 3 edges. These graphs are both trees, but they are said to be non-isomorphic because there is no way to move around the vertices and edges of K_{1,3} to obtain ... 1 While (2,5,8) is an inclusionwise maximal independent set, it is not a maximum cardinality independent set. The graph parameter \alpha(G) should be understood to mean the latter. In the example you give, (1,3,5,7,9) is another maximal independent set, and this one has greater cardinality. The existence of this set shows that we have \alpha(G) \geq 5. It ... 0 For simultaneously diagonalizable matrices A and B, it is easy to find a unitary P such that A=P^TBP. E.g. WLOG diagonalize on some order the eigenvalues such that A = V^TDV and B=W^TDW for unitary V, W and common diagonal matrix D; then we have a solution P=V^TW. However, P is not unique. In fact, the set of solutions for P is a set ... 2 An n-gonal prism (a prism where the two "ends" are not triangles but n-sided polygons) is a connected, planar, 3-regular graph on 2n vertices. It's not isomorphic to Greg Martin's family of examples, since (for n>3) the prism has no 3-cycles. I can't draw pretty pictures, but it's a cycle A_1,\dots,A_n inside a cycle B_1,\dots,B_n, with ... 0 HINT: Let G_1 and G_2 be disjoint copies of K_{3,3}. Let v be a new vertex not in G_1 or G_2. Connect v to two vertices of G_1 and to two vertices of G_2 to form G. 1 Yes, this is correct. In a complete graph, any two distinct vertices have an edge connecting them, so in particular if you take a vertex from the 4-clique and a different vertex from the 3-clique, there is an edge between them. 1 on Google+ one of friends of mine give an answer: Chordak graph --> https://en.wikipedia.org/wiki/Chordal_graph and it looks pretty good... 0 Since your graph is regular and class 1, every vertex is incident with exactly one edge of each color. So for any given color, the edges of that color form a perfect matching. 4 The number of vertices alone is not sufficient to determine the number of edges From Euler's formula we know that$$v-e+f=2,$$where v is the number of vertices, e is number of edges and f is number of faces (including the outer one). Now you now additionally, that boundaries of faces have three edges. However, there is one exception, which is the ... 1 The answer is simple By Dirac (1952) : A simple graph with n vertices (n ≥ 3) is Hamiltonian if every vertex has degree \frac{n}{2} or greater. See https://en.wikipedia.org/wiki/Hamiltonian_path Since n is even, then 2 does not divides n-1. Thus$$d(v)\geq \frac{n}{2}

1

First, it’s always true that $\chi(G)\ge\omega(G)$, so your real problem is to show that $\chi(G)\le\omega(G)$ if $\overline{G}$ is bipartite. Note that it need not be true that $\chi(\overline{G})=2$: the chromatic number of a bipartite graph is $1$ if the graph has no edges. In that case $G$ is a complete graph, and the result is trivial, so I’ll assume ...

1

An empty graph on $n$ vertices has $n$ connected components, Suppose you have a graph and add an edge, then the number of connected components is reduced by at most one ( since this edge touches at most two connected components). Therefore a connected graph on $n$ vertices has at least $n-1$ edges). Suppose a connected graph on $n$ vertices has $n-1$ ...

0

It is exactly that. $N(X)$ is the set of neighbours, the vertices adjacent to at least one vertex in $X$. On the other hand $"| |"$ denotes cardinality, or number of elements. So $|N(X)|$ is exactly what you thought, the number of vertices in the graph that are adjacent to at at least one vertex in $X$.

0

That is by definition the size of the neighborhood of $X$. That is, it is the total number of vertices in $Y$, such that they are connected by an edge to some vertex in $X$. Of course, we only count each vertex once, regardless of connectivity so long as it is in the neighborhood of $X$.

Top 50 recent answers are included