Tag Info

Hot answers tagged

3

And I was thinking .2121 was the second solution. Although 4 is fine, too.


3

$n=3$ is not a solution. $n=4$ is solution. If $n\ge 5$, then $n^{n-2} \ge n^{5-2}=n^3 \ge 5^3>16$, so, $n=4$ is the only solution.


3

This would be the corona of $K_n$ and $K_1$, usually denoted $K_n \circ K_1$. The original definition was by Harary and Frucht in 1970 in their paper "On the Corona of Two Graphs" See this question for an application of it to more general graphs: Eccentricity in corona product


3

Maybe the easiest example of a graph with critical vertices and no critical edges is a star graph $G=(V, E)$ where $V=\{c, v_1, v_2, v_3, ..., v_{k}\}$ and $E=\{(c, v_1), (c, v_2), (c, v_3),...,(c,v_k)\}$. Note that the chromatic number is $2$, but if vertex $c$ is deleted then the chromatic number is $1$. However, if any edge is deleted then the chromatic ...


3

Maximum means that there is no larger clique in the graph. Maximal mean that the given clique cannot be extended to a larger one. As an example, consider $G=K_{3}\cup K_{4}$ the disjoint union of two cliques. The size of the largest clique in the graph is $4$ and the $K_4$ is a maximum sized clique. The $K_{3}$ is maximal, meaning that if you add any ...


2

By Brooks's Theorem, the graph is $3$-colorable. We can thus pick a $3$-coloring of the graph, with vertex colors red, green, and blue, such that there are $\leq n/3$ blue vertices. For each blue vertex $v$: If it has $\leq 1$ red neighbors, recolor $v$ red, and delete the red-to-red edge if we introduce one. Otherwise, $v$ has $\leq 1$ green neighbors, ...


2

There are two difficulties that causes the algorithm to fail: the order the colors are selected in is not specified, the order that neighbors of a vertex are colored is not specified. As an example, here is how it fails: $V(G)=\{1, 2, 3, 4, 5, 6\}$ and $E(G)=\{(1,2), (1,3), (2,3), (2,4), (2,5), (4,5), (3,5), (3,6), (5,6)\}$ (three triangles that pairwise ...


2

You have to use the fact that the graph is $4$ - regular, so all degrees of vertices are $4$. Then, remember that the sum of all vertex degrees is closely connected (i.e. there exists a formula to connect them) to the number of edges. Now, the sum of vertex degrees is simply $4\cdot n$, since you have $n$ vertices and each has degree $4$. Plugging this ...


2

Take a maximal path $v_1,v_2\dots v_n$, since the path is maximal all of the neighbours of $v_1$ are in the graph since othwerwise the path could be elongated. Because of this $v_1$ has at least $\delta(V)$ neighbours in the graph. The one that is farthest away will be $v_k$ with $k\geq1+\delta(V)$. Therefore taking $v_1,v_2,v_3,\dots v_{k-1},v_k,v_1$ ...


2

Hint: Start with $v_1$, the vertex with degree $d_1$ in the original graph. How would you modify it so as to increase its degree to $K$, attach $K-d_1$ new vertices each with degree one, and leave all other original vertices untouched?


2

Lets suppose your graph has vertices $v_1,\ldots, v_n$. $W$ is the weighted adjacency matrix, i.e. the value $W_{ij}$ is the weight of the edge $e = \{v_i,v_j\}$ ($W_{ij} = 0$ if there is no edge between $v_i$ and $v_j$). $D$ is the diagonal matrix s.t. $D_{ii} = W(i) := \sum_j W_{ij}$, i.e. $D_{ii}$ is the weighted vertex-degree of $v_i$. The ...


2

If you allow infinite graphs, then the set of natural numbers $\mathbb{N}=\{0,1,2,3,\ldots\}$ with consecutive numbers considered adjacent is a counterexample: the vertex $0$ has degree $1$, while all others have degree $2$, but the graph contains no cycles.


2

The graph in question has an odd number of vertices, but that does not contradict the theorem. The theorem says that it will have an even number of vertices with odd degrees, which it does: it has two, namely, $v_0$ and $v_1$, each of degree $1$.


2

You are correct on part (A). In (B) such a graph is not possible. Because if you look at the vertex that has degree 6 it must be connected with all the other vertices in the graph. But then there is a vertex of degree 5 it will be connected to the degree 6 vertex plus 4 other vertices. But there are two vertices of degree 1 that are already exhausted by ...


2

Here are two discs, but there are only $6$ sectors with matching colours: Here I've rotated the outer disc, and now $10$ sectors match.


2

The following fact holds: Let $G$ be the Petersen graph and $C$ be a 6-cycle in $G$, then the subgraph of $G$ induced by $V(G) - V(C)$ is a claw, vice versa. In the figure above, orange is a 6-cycle and blue is a claw. There is a one-to-one correspondence between the 6-cycles and the claws. Thus we only need to count the # of claws. Note that the ...


2

Here are two 6-cycles in the Petersen graph: By cyclic rotation, we generate the 10 6-cycles. To prove these are the only $6$-cycles: We must have precisely $2$ pink-to-blue edges. To form a cycle, the number must be even, and there are not enough pink (or blue) vertices to have $0$, and we can't have $4$ because they cannot be connected to form a ...


2

A bit of a late answer, but I think it's interesting. There's this thing called the graph arboricity : See here. It's the minimum number of edge-disjoint forests needed to cover every edge exactly once. It's actually equivalent to the number of spanning trees needed to cover every edge (with possible repetitions). We have to assume that the graph is ...


2

I'll write up my suggestion here as we aren't supposed to have long discussions in comments. There are two steps to solving a problem like this for small graphs: 1) List all the subgraphs. That looks like what you have in your picture. 2) Compare all the pairs of subgraphs to see if they are isomorphic. As was suggested in the comments, the lower left ...


1

You must start with $be$, since it’s the unique edge with least weight. At each step you must choose an edge of minimum possible weight that does not complete a cycle, so your next edge can be any of the edges of weight $3$: $ad$, $ef$, or $hi$. (Note that there is no requirement that your set of edges form a tree at this stage.) No matter which one you ...


1

Let $$A = \left[\begin{array}{ccc} 0 &1& 0\\ 0 &0 &1\\ 1 &0& 0 \end{array}\right],$$ then $$ A^1 = \left[\begin{array}{ccc} 0 &1& 0\\ 0 &0 &1\\ 1 &0& 0 \end{array}\right]\quad A^2 = \left[\begin{array}{ccc} 0 &0& 1\\ 1 &0 &0\\ 0 &1& 0 \end{array}\right]\quad A^3 = ...


1

Prove Dirac's fan lemma first: If $G$ is a $k$-connected graph $x$ a vertex, and $V$ a set of $n\geq k$ vertices then there exists a family of $k$ vertex disjoint paths (disjoint except for vertex $x$) from $x$ to $k$ of the $n$ vertices (all of them distinct,thanks to the fact they are vertex disjoint) To prove this just add a vertex $y$ that is connected ...


1

Let me first treat part one, since this is the easiest part Part 1: the number of subsets of a given set $X$ is $2^{|X|}-1$, where $|X|$ is the number of elements in $X$. I had to substract the $1$ because you are not interested in the empty subset $\emptyset$. A way to see why this is the number of options is the following: consider a set of $|X|$ slots, ...


1

(Assuming your condition should be that the independent set is of size at least half the number of vertices in $H$.) Recall that a graph is bipartite if and only if it has no cycles of odd length. So if a graph satisfies your condition but is not bipartite, take $H$ to be an odd length cycle. Do you see the contradiction?


1

Yes the result is still true for $k>2$. You could define the required automorphisms directly without too much trouble, but maybe an easier way is to look at the complement of $T_{k,km}$, which is nothing but a disjoint union of $k$ copies of $K_m$. Since such a graph is clearly vertex-transitive, so is $T_{k,km}$.


1

A complete $k$-partite graph such that one of the partite sets has only one vertex, and each other partite set has at least 2 vertices will work. Deleting any edge will not decrease the chromatic number, but deleting the vertex in its own partite set will decrease the chromatic number.


1

Knowing that $K_{3,3}$ is non-planar helps. Also, by Kuratowski's theorem any graph that has a subgraph homeomorphic to $K_{3,3}$ is also non-planar. This should narrow it down quite a bit because we can now conclude that $K_{3,n}$ and $K_{m,3}$ are non-planar for $m,n \geq 3$. Can you take it from here?


1

As Perry pointed out in the comments, there is a gap in the logic. There do exist graphs that are not $K_5$ or $K_{3,3}$ with $\delta (G) \ge 3$ such that $G$ is non-planar. However, assume that such a graph is given given as a counter example. Then since it is non-planar, it must have some subgraph that has a vertex of degree 2. Thus, some vertices or ...


1

Let the first vertex $A$ have three neigbours $B,C,D$. Let each of these have another neighbour $B',C',D'$. Join $B',C',D'$ be edges. If your algorithm starts at $A$, it assigns colour $1$ to $A$, then the same new colour $2$ to $B$,$C$, an $D$. This makes $B,C,D$ indistinguishable for the rest of the algorithm, i.e., we essentially colour a $K_4$ with ...


1

135 is not a $2$-clan because the induced subgraph on 135 does not have diameter at most 2 (it is not connected, so the diameter is infinite). 135 forms a 2-clique because it is a set in the graph where the pairwise distances between the points is at most 2. $k$-clique looks at sets inside the whole graph. $k$-clan looks at induced subgraphs.



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