# Tag Info

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

3

Let $G$ be a simple graph (non necessarily finite—see postcript) with minimum degree $\delta$ and order $|V(G)|\ge2\delta.$ Let $M$ be a maximum matching in $G,$ and assume for a contradiction that $|M|=m\lt\delta.$ Then $W=V(G)\setminus V(M)$ is independent and $|W|\ge2.$ Choose two distinct vertices $x,y\in W.$ There are at least $2\delta$ edges between ...

3

The problem of whether there exists a nontrivial graph automorphism reduces to graph isomorphism, and is not known to be any easier. Here is a way I thought of explaining that problem: Start with a supply of yarn and some jacks. Each jack represents some country in the world. If two countries share a border, tie those two jacks together with a piece of ...

2

A very artificial example. Explain the context of Hall's theorem and how we model it with a bipartite graph. That is, you have $n$ boys and $n$ girls and know which one likes who. Call this the likeness graph. If you have only two people then the situation is pretty simple. Either they like each other or they dont - you have two non-isomorphic instances ...

2

I mean that my proof is correct.

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

2

$\frac{(n-k)(n-k+1)}{2}$ refers to the maximum possible number of edges of a simple graph (no double edges, no loops) on $n$ vertices and with $k$ connected components.

2

Here are some hints: (3) Take a vertex $v$ with $\Delta(G)$ neighbors, and try coloring the edges incident to $v$. How many do you need just for that vertex ? (4) Just do what you did for (2). Color the edges with $\chi'(G)$ colors. The edges belonging to a particular color class cannot touch each other, so they form a matching.

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

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

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

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

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

1

Take $V=\{ x_1, x_2 \}$ and $E=\{\overline{x_1 x_2 }\}.$

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

Take a largest matching $M$ (of size $\alpha^\prime(G)$) and include both endpoints of each edge into a vertex cover $C$. Clearly, $\lvert C\rvert \leq 2\alpha^\prime(G)$: it remains to prove that $C$ is indeed a vertex cover (this will give the result, since the smallest vertex cover will be of size at most $\lvert C\rvert$). For more, put your mouse over ...

1

The error comes from replacing $\binom{k}{2}$ with $k^2/2$. Leave it as $k(k-1)/2$. Then the exponent on the 2, after dividing by $k-2$ becomes $${\frac{k(k-1)}{2}\cdot\frac{1}{k-2}}= (\frac{k}{2}-\frac{1}{2})\cdot(1 +\frac{2}{k} + O(1/k^2)) = \frac{k}{2} + \frac 12 + o(1).$$ If you do Erd\H{o}s's original argument and leave $\binom{k}{2}$ as $k(k-1)/2$ you ...

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

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

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

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

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

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.

1

Suppose $|V| \ge 2$. Recall that the sum of the degrees of all vertices is $2|E|$. Since The graph is connected there cannot be a vertex of degree $0$. Thus as $2|V|> 2|E|$ there is a vertex of degree one. Removing that vertex and the adjacent edge does not change that the graph is connected. And if the graph after removal is a tree, so is the graph ...

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

1

Yes you're right. A trivial component is a connected graph with no edges so it has degree 0 and is thus an isolated vertex. However. A trivial graph is the complement of $K_n$ and that is probably what the (graph) part under 2. wants to emphasize.

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

The above equations can be represented by the following augmented matrix: \left(\begin{array}{rrrrrrrr|r} 0&1&1&0&0&0&0&0 & 12 \\ 0&0&1&0&0&1&1&0 & 0 \\ 0&0&0&1&0&1&0&1 & 0 \\ 0&0&1&0&-1&1&0&1 & 0 \\ ...

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

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