New answers tagged

2

Let $G$ be a graph with exactly one perfect matching $M$, $2n$ vertices and $m$ edges. Let $v$ and $w$ be two vertices that are endpoints of an edge of $M$ and let $d(v)=t$. A neighbor $u$ of $v$ different from $w$ is endpoint of an edge $e_u$ of $M$ and $w$ may not have an edge to the other endpoint of $e_u$ or we find an alternating 4-cycle, which would ...


0

Even though this question seems to be of no interest to anyone I still thought it would be good form to post here a counterexample I found since posting: Suppose (aiming for a contradiction) that the graph contains a cycle $C$ of the form described in the question. Picking any of the red edges it is easy to conclude that it is absolutely necessary that ...


0

Threads mentioning cut space and cycle space in Math.SE The cycle space and cut space are orthogonal complement: "Let $G$ be a graph. The cycle space and cut space are orthogonal complement if and only if the graph $G$ has an odd number of spanning tree." where trying to find a proof. Consequences of cycle space cut space duality Decomposition of graph to ...


1

No, this is not a simplicial triangulation. But yes, triangles are allowed to have nothing on the boundary of the original triangle (though they are of course inside that triangle). Note by the way that only five triangles in the above triangulation have a vertex in common with the original triangle, which is not the same as having a vertex on the boundary ...


1

The triangle immediately to the left of triangle $A$ (lets call it $X$) and the large triangle to its right (the one that includes side $RB$) intersect, but have no common vertex or side. So this is not a simplical subdivision. The same could be said for triangle $X$ and the triangle directly below it (the one without the label $A$ in its interior) as well.


0

Your proof is fine, and the result is well known. The inequality can be strict, e.g., when $G=K_{3,3}.$ For a finite graph $G$ and a finite cardinal $d$ the following statements are easily seen to be equivalent: for every nonempty set $S\subseteq V(G)$ there is a vertex $v\in S$ such that $|N(v)\cap S|\le d;$ $V(G)$ can be totally ordered so that each ...


2

There is no other form to prove your statement than analysing all cases. For example you can proceed as follows: If the network has no switch, you have the circle. Assume there is at least one switch, take any switch, number the ends of any switch with 1, 2, 3, the two last (2 and 3) being symmetric. Assume you can get from 1 to 2 without passing ...


2

A simpler example for odd $n=2k+1$ would be the complete bipartite graph $K_{k,k+1}$. It is easy to see that there is no solution for $n=4$, and there is none for $n=6$ either. In fact I haven't found any solution with an even $n>2$.


3

I am considering the odd $n$ case, you will figure out the even case. Take $G=(V,E)$ where we note $V=\{v_1, ..., v_n\}$ and $\forall (i,j)\in[1,\frac{n+1}{2}], (v_i,v_j) \in E$ $\forall (i,j)\in[\frac{n+1}{2},n], (v_i,v_j) \in E$ (Intuitively, you have two complete graphs of size $\frac{n+1}{2}$ which you stuck by one node) Since you have to go only ...


2

According to the De Bruijn–Erdős theorem, a graph $G$ is $3$-colourable if and only if every finite subgraph of $G$ is $3$-colourable. Hence, if $V(G)=\mathbb N=\{1,2,3,\dots\},$ then $G$ is $3$-colourable if and only if, for every $n,$ the subgraph $G_n$ induced by $\{1,2,3,\dots,n\}$ is $3$-colourable. I'm sure you can figure out how to construct a formula ...


1

First we establish the upper bound by exhibiting a 3-(total-)coloring for $C_n$ when $3\mid n$ and a 4-coloring for all $n$. When $n\mid 3$ color the vertices red, green, blue cyclically. Color the edge between two vertices with the only color that is not used on its endpoints. This is a proper total coloring with 3 colors (verify!). When $n$ is even we ...


1

You want to sort the vertices so that whenever there is an edge $i \to j$, $i$ comes before $j$. One way to do that is to count the number of vertices reachable from each vertex, and sort in decreasing order of that. If $A$ is the original adjacency matrix ($n \times n$), then $j$ is reachable from $i$ iff $((I+A)^{k})_{ij} > 0$ where $k \ge n-1$. So ...


1

I find a proof from a paper by Erdos. Below is the detail. Put $d(v_i) = |N(v_i)|$. Without loss of generality, assume that $d(v_1) \geq d(v_2) \geq \cdots \geq d(v_n)$. In addition, let $c(v_i)$ denote the number of $v_i$'s neighbors that are not neighbors of $\{v_1, \cdots, v_{i-1}\}$. Because $G$ does not contain $K_{2,3}$, $|N(v_i) \cap N(v_j)|\leq ...


0

Assume for a contradiction that $N(u)\subseteq N(v).$ Since $G$ is $k$-critical, $G-u$ is $(k-1)$-colorable. Take a proper coloring of $G-u$ with $k-1$ colors, and extend it to $G$ by giving $u$ the same color as $v.$ Since $N(u)\subseteq N(v),$ it is clear that this is a proper coloring of $G$ with $k-1$ colors, contradicting the assumption that $G$ is ...


3

I did some experiments for regular polygons, for up to $n=24$ (click to enlarge): These experiments suggest that If $6\vert n$ you get a $3$-cycle Else if $2\vert n$ you get a $4$-cycle Else you get a $6$-cycle That you can get the $3$-cycle for anything that has edges aligned as a hexagon has them is pretty obvious. On the other hand, for reasons of ...


0

We know that, in any $k$-critical graph, the degree of each node is at least $(k-1)$. (Otherwise you could arbitrarily colour all other nodes and then still have choice for the colour of a less-connected node - meaning you could discard it without reducing $k$). This gives you: $$ q \ge \frac 12 . n . (k-1) $$ Take it from there to get your answer.


3

If by "disjoint" you mean "vertex-disjoint", this is false, e.g.: +------ | | | V v1 -> a -> v2 -> c -> v1 | ^ | ^ | | | | +---> b ---+ +----+ (where $v_1$ appears twice for graphical convenience but is the same vertex). If by "disjoint" you mean ...


1

Let $G$ be an $n$-vertex graph that does not contain $K_{2,3}$. Let $m$ be the number of edges of $G$. We count the number $N$ of pairs $(v,S)$ where $v$ is a vertex of $G$ and $S$ a pair of vertices such that $S\subseteq N(v)$. We count $N$ in two different ways. First we start with a vertex $v$: each pair $S$ of two vertices from $N(v)$ gives a desired ...


0

I am not sure the identites you state are useful in this case. Let $G$ be properly colored. Since there has to be at least one edge between any two colors clases, we have $$e \geq {\chi(G) \choose 2} = \chi(G)(\chi(G)+1)/2 \geq \chi(G)^2/2$$ and the result follows.


0

We prove by induction on $d$. If $d = 1$ there is an edge, and this is the needed path. Suppose $d ≥ 2$, the result is true for $d < D$, and minimum degree of your graph is $d$. By the induction hypothesis $G$ has a path $P$ of length at least $d − 1$. If the length of $P$ is at least $D$, then we’re done. So suppose the length is $D − 1$ and the sequence ...


2

Using the definition of an adjacency matrix $A$, it follows that $[A^2]_{ii}$ is equal to the number of edges connected to $i$, i.e. the degree of $i$: $d_i$. Now recall (or easily rederive) that $\sum_i d_i=2e$. Finally use the fact that the eigenvalues of $A^2$ are $\lambda_i^2$ along with the fact that their sum is equal to the trace of $A^2$.


6

I assume $P_3$ is the graph *---*---* An embedding of this into $K_{10}$ is simply a labeling of it with three different numbers from $\{1,2,\ldots,10\}$. To choose such a labeling, first pick the label of the middle node; this can be done in $10$ ways. Then pick the numbers that will label the two end nodes; this can now be done in $\binom92$ ...


1

You want to prove that if the adjacency matrix of the graph $G$ is $A$, then the adjacency matrix $\overline{A}$ of the complement graph $\overline{G}$ is $J-I-A$. Observe that vertices $i$ and $j$ are adjacent in $G$ iff vertices $i$ and $j$ are nonadjacent in $\overline{G}$. Hence, the edge set of $G$ and of $\overline{G}$ together form the edge set of ...


2

Harary's "Graph Theory" book has a chapter on line graphs (see Chapter 8), where Whitney's isomorphism theorem (Theorem 8.3) is proved.


0

Suppose the graphs $G$ and $G'$ are isomorphic, and suppose $\phi: V(G) \rightarrow V(G')$ is a bijection from the vertex set of $G$ to the vertex set of $G'$ which preserves adjacency. If $\phi$ takes $u$ to $u'$, then $\phi$ takes the neighbors of $u$ to the neighbors of $u'$. This is because the isomorphism $\phi$ preserves adjacency. So if $u$ and $x$ ...


0

A graph having edges with real weights has an adjacency matrix $W$ with real entries. The example graph given in the Wolfram page has the adjacency matrix shown below. \begin{equation*} \begin{bmatrix} 0 & 1.6 & 1.4 & 0\\ 1.6 & 0 & 1.2 & 0\\ 1.4 & 1.2 & 0 & 2.5\\ 0 & 0 & 2.5 & 0 \end{bmatrix} \end{equation*} ...


1

Well for the complete graph $K_n$ one sees that all vertices are connected by an edge. As such each $a_{ij}=1$. Hence $A(K_n)$ is the matrix consisting of all ones. One can deduce similar arguments for $W_n$. Notice that for the wheel graph, there is one special point and the other points are all identical. You could try to give an answer for small $n$ and ...


1

Each permutation $g \in S_n$ can be represented by an $n \times n$ permutation matrix $P(g)$ defined by $P(g)_{ij} = 1$ iff $g$ maps $j$ to $i$, and $P(g)_{ij}=0$ otherwise. Let $A$ denote the adjacency matrix of the graph $G$. It can be verified that a permutation $g$ is an automorphism of the graph $G$ if and only if $P(g)^{-1}AP(g) = A$. In other ...


0

First question: You are basically right, but let's lay some notation. I assume your graph is finite (finite edges and finite vertices). Let a path be a set $\{e_i\}$ for $i=1,2,...,k$ where each $e_i$ is an edge and the $e_i$ lands where $e_{i+1}$ starts, for all $i=1,2,...,k-1$. Now, given this path, call the probability of following it ...


2

You can label each vertex $V= \{v_1,\cdots,v_6\}$ and then create the adjacency matrix $$A_{i,j}=\left\{\begin{array}{rl} 1 & v_i \text{ and } v_j \text{ share an edge} \\ 0 & \text{ otherwise} \end{array}\right.$$ Then find the eigenvalues of $A$ computationally using Mathematica, WolframAlpha, or Matlab (or any other program you'd like).


7

$K_{3,3}$ is a minor of $Q_4$, hence $Q_4$ is not a planar graph, and obviously $Q_4$ is a minor of $Q_n$ for any $n>4$, hence the only planar hypercubes are $Q_n$ with $n\leq 3$. Another approach: $Q_4$ is a triangle-free graph, but any planar and triangle-free graph with $n$ vertices has at most $2n-4$ edges. $Q_4$ has $16$ vertices and $32>2\cdot ...


2

Your definition of automorphism is a bit too strong, I feel. Leaving something "unchanged" in the sense that the numbers in each cell of a matrix is a VERY strong notion of equality. However, you're not using that definition of equality for graphs. As corrected by Morgan Rodgers, strict equality actually works fine. The adjacency matrices are indeed ...


0

HINT: The complete graph on $4$ vertices has $\binom{4}2=6$ edges, so any graph on $4$ vertices with $5$ edges is just $K_4$ minus one edge.


1

Let $G$ be a graph with chromatic number $2$ and list chromatic number $3,$ e.g. $G=K_{3,3},$ or just take $C_6$ and add an edge joining two diametrically opposite vertices. Take the graph $3G$ (the union of three vertex-disjoint copies of $G$); add a new vertex $v$ and edges joining $v$ to every vertex of $3G.$ You can easily show that the resulting graph ...


4

Yes, you are checking whether there is an automorphism of $G^{\prime} = \bar{G}_{1} \cup \bar{G}_{2}$ that swaps a vertex of $\bar{G}_{1}$ with a vertex of $\bar{G}_{2}$. You are using Graph-Aut as an oracle, so what you will do is use Graph-Aut to find the automorphism group of $G^{\prime}$ (returned as a set of generators), then just look at whether any of ...


3

The minimum number of edges that need to be removed to disconnect the graph is $3$, and there are just $4$ ways to do this: remove all of the edges incident at one vertex of degree $3$. There are $9$ ways to remove a set $E$ of edges so that (a) the resulting graph is disconnected, and (b) removing any proper subset of $E$ leaves a connected graph. However, ...


2

The definition of the fundamental group does not depend on any choice of a spanning tree. A spanning tree is just used to get an explicit description of a group that the fundamental group is isomorphic to. So it would be no problem if it turned out you could get free groups of different rank by choosing different spanning trees--this would just be a proof ...


1

$\pi_1(A)$ and $\pi_1(B)$ are trivial since they are contractible, $\pi_1(C)$ is the free group generated by 2 elements since $C$ retract to the bouquet of two loops.


1

The number of strings of length $n$ having exactly two blocks of $1$'s, the first of length $a$, the second of length $b$, is readily computed to equal $n+1-a-b\choose2$, provided $n\ge a+b$. This gives us the number of vertices as $$v_n={n-1\choose 2}+2{n-2\choose 2}+3{n-3\choose 2}+2{n-4\choose 2}+{n-5\choose 2} =\frac{9n(n-7)}{2}+60$$ To count the edges, ...


2

Now if $Q$ an increasing graph property (if $G \in Q$, then the graph obtained by adding any arbitrary edge to $G$ is also in $Q$) such that the null graph on $n$ vertices is not in $Q$ and $K_n$ is in $Q$, then $$ p \rightarrow f(p):=Pr ( G(n,p) \in Q ) $$ is a strictly increasing function with $f(0)=0$ and $f(1)=1$. This is because for fixed $n$, $$ f(p) ...


1

The ($\Rightarrow$:) part is almost complete, except where you are not sure. We pick $x \in X$ and $y \in Y$, and we know that there is a path between them. Let the vertices in this path be $x, a_1, a_2, \dotsc, a_n, y$. The first vertex is in $X$, and the last vertex is in $Y$; all vertices are either in $X$ or $Y$ and never in both. Consequently, there ...


0

$(x-1)(x+1)^2(x-\frac{1-\sqrt{17}}{2})(x-\frac{1+\sqrt{17}}{2})$.


0

First, let me generalize the statement a bit: Let $G=(V,E)$ be a connected graph with chromatic number $\chi(G)\in\mathbb{N}$ (i.e. the smallest number of colors needed for a proper coloring of $G$). Then there exists a path of length $\chi(G)-1$ through vertices of different colors. Note that the existence of a path of length $\chi(G)-1$ also yields the ...


1

What does each column $b_j$ of B encode, geometrically? Can you show that $b_i\cdot b_j$ computes the number of edges that vertex $i$ and $j$ share? The theorem should now be straightforward: consider the three cases where two vertices $i,j$ are adjacent, not adjacent, and equal.


1

Archaick has already given you a simple exposition of your correct approach. I would like to point out an interesting fact, which is that it is actually crucial to use the Eulerian property of $G$, which proceeds via the theorem that every finite graph with even vertex degrees has an Eulerian loop, and hence any two vertices are in some cycle. The reason is ...


1

I disagree with Hagen that you have the right idea. It is a serious logical error you made concerning induction, and I encourage you to read and fully grasp http://matheducators.stackexchange.com/a/10034/1550 before attempting induction problems. After you read that then read my answer. I give you any tree $T$ and graph $G$ such that every vertex in $G$ has ...


1

You have the right idea, but you should not modify $G$, esp. you cannot expect to obtain a given degree-$e$ graph from an unspecified degree-$(e-1)$ graph. Instead try the following: Let $T=(V_T,E_T)$ be a tree with $|E_T|=e$ edges (and hence $|V_T|=e+1$ vertices) and let $G=(V_G,E_G)$ be a non-empty, simple graph be given such that all vertices of $G$ ...


11

Your description of how the hydra "regenerates" is incorrect. You don't add copies of the entire tree above the grandparent node, only part of the tree above the grandparent node that starts with going to the parent node. This means that after cutting off a head from $((xx)(xx))$, you get $((xx)(x)(x))$, because you only duplicate the $(x)$ part you had ...


0

For the above problem I got the counter example from the following link. http://mathoverflow.net/a/239446/78180



Top 50 recent answers are included