# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

2k views

### Graph theory: If a graph contains a closed walk of odd length, then it contains a cycle of odd length

I am trying to prove what's on the title. I have been working on it for some time already and the problem I have is that I can't seem to prove that the cycle I get at the end is of odd length. Here ...
43 views

### Graph theorem(homework) [duplicate]

This is the theorem If $G$ is a graph, there are at least $2$ vertices(points ) always have the same degree. e.g: I have graph $G$, $(U,V)$ ,$4$ vertices $(e1,e2,e3,e4)$ ,and $4$ edges. So the ...
31 views

920 views

### Given two non-isomorphic graphs with the same number of edges, vertices and degree, what is the most efficient way of proving they are not isomorphic?

After being given the following two graphs with the same number of edges, vertices and degree, I'm trying to show that they are not isomorphic. At least they seem to be non-isomorphic from the time I ...
53 views

### Graphs: Show that for $K_{17}$ there exist an edge coloring with 8 colors with a circle colored by one color.

Show that for $K_{17}$ there exist an edge coloring with 8 colors with a circle colored by one color. My work so far: We know that for each vertex, $v_i$, it's degree is $d(v_i)=16$, because the ...
90 views

### Question on Planar Graph

Let $\delta$ denotes the minimum degree of vertex in a graph. For all planar graphs on $n$ vertices with $\delta\geq3$, which of the following is TRUE? $i)$ In any planar embedding, the number of ...
214 views

### Proving a cut vertex in a tree, $T$, is an end-vertex:

If $T$ is a tree of order at least $3$, then $T$ contains a cut vertex $v$ such that every vertex adjacent to $v$, with at most one exception is an end vertex. I know that if $T$ is a connected graph ...
193 views

### Do subgraphs imply non-planarity if they correspond to subdivisions of K3,2 and K5 graphs?

I was given this problem: "Determine which of the graphs in figure 2 are planar. In each case either draw a planar graph or exhibit a subgraph which is a subdivision of K3,3 or K5". I did the first ...
48 views

### A stronger condition than planar graph?

Is there a name for this condition on a graph: a graph that can be embedded in the plane (planar), in such a way that of its univalent vertices do not lie inside any face? So, one can think of this ...
78 views

3k views

### Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$

Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$. How would I show this? I understand that a cycle is a sequence of non-repeated vertices and the ...
3k views

### Prove that if there is a walk from u to v then there is also a path from u to v.

Let G be a graph and let u and v be two of its vertices. Prove that if there is a walk from u to v then there is also a path from u to v. Using induction on length of a path, how can I solve this? ...