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.

learn more… | top users | synonyms

2
votes
2answers
83 views

a game of coloring edges of graph

I have a clique of size 5 which is partially colored(black or white). I have to color remaining edges so that each of the triangle has either 1 or 3 black edges. How should I go about coloring the ...
2
votes
1answer
47 views

In search of a symmetric homogeneous graph with a pivotal origin

I'm trying to design a computer game and I need a symmetric homogeneous graph with a pivotal origin which will act as the map of the game (players will walk according to it). Here's an example of ...
2
votes
1answer
199 views

Graph Theory Cycles in Nonseparable graphs

Let k be the maximum length of a cycle in a nonseparable graph G. Prove that if C and C' are any two k-cycles in G, then C and C' have at least two vertices in common. Nonseparable meaning ...
3
votes
1answer
189 views

Graph Theory Spanning Trees and Diameter

Show that for every connected graph G there is a spanning tree T of G such that diam(T) ≤ 2diam(G). I am having trouble approaching this problem. diam(T) means diameter of T, which is the ...
0
votes
3answers
65 views

In a graph $G$, $d(u,v)=m$.Find $d(u,v)$ in $G^n$

Let $G$ be a graph . we define $G^{n}$ as: $V(G)=V(G^{n})$ and for $v,u \in V(G)=V(G^{n}) $ ,$u$ and $v$ adjacent in $G^{n}$ if $d(u,v)\le n$.Now suppose in some graph $G$ , $d(u,v)=m$.Find $d(u,v)$ ...
1
vote
1answer
58 views

Explain this theorem by Hakimi?

This is a theorem by S L Hakimi. Can anyone explain what this theorem is trying to say? Theorem 1. The necessary and sufficient conditions for positive integers $d_1,d_2,\cdots, d_n$ to be realizable ...
-1
votes
1answer
81 views

The smallest number of points in a cubic graph with a edge is 10.

The smallest number of points in a cubic graph with a edge is 10. I think this number is 6. but I don't know prove this answer.
2
votes
1answer
429 views

Prove $|V(G)| \ge k^2 + 1$ when all vertices in a graph $G$ have degree at least $k$

Suppose the shortest cycle in graph $G$ has length $5$. Prove that if every vertex of $G$ has degree at least $k$, then $G$ has at least $k^2+1$ vertices. So far, I have $k \neq 0$, $k \neq 1$, or ...
0
votes
1answer
108 views

Mathematical formulation for maximum sum of edge weights

For my academic research purposes, I have a situation as below. The initial problem looks as in below figure. I need to find one match for each of P1,P2,P3 from the right side such that the sum of ...
1
vote
1answer
153 views

In how many ways can k vertices be partitioned into k/2 pairs?

This is supposed to be a really trivial answer I think, but I guess I'm missing something, because it confuses me a lot. Suppose G has k vertices of odd degree. In how many ways can the odd vertices ...
1
vote
2answers
61 views

Prove that G is a complete graph.

I need help with this problem: Let G be a graph such that, for all vertices a & b, the chromatic number of G - {a,b} = the chromatic number of G - 2. Prove that G is a complete graph.
0
votes
0answers
62 views

Are there motivating examples for graphs with negative edge weights?

Every example I come up with for a directed graph with negative edge weights seems contrived in some way. Can anyone name some real ones? Even better if they aren't obviously networks to start with.
2
votes
0answers
68 views

Genus of complete 4-partite graph.

What is the genus of the graph $K_{mn,n,n,n}$, where $m$ and $n$ are positive integers? I know that the genus of the graph $K_{mn,n,n}$ (see A. T. white, Graphs, Groups and Surfaces, Theorem 6-39) is ...
1
vote
1answer
40 views

K-tree and Partial k-tree

I have some confusion in understanding the definitions of $k$-tree and partial $k$-tree. I have refereed to wikipedia for these definitions but they are not clear for me. Can somebody explain these ...
0
votes
1answer
42 views

Decomposing $K_v - K_u$ into Hamilton paths where $v = u^2 - u + 1$.

A decomposition of a graph $G$ into subgraphs $H$ is a collection of graphs all isomorphic to $H$ which are edge-disjoint in $G$ and together cover all the edges of $G$. Let $u \geq 1$ and $v = u^2 ...
1
vote
0answers
34 views

Graphs: First Order Characterisation Of A path

Whilst reading this: http://dtai.cs.kuleuven.be/krr/files/seminars/IntroToFMT-janvdbussche.pdf a seminar on finite model theory, I thought that something was wrong. "Given a Graph G and a Binary ...
2
votes
1answer
40 views

Tree of a graph

Let $T$ be a tree such that for all edges $e\in E(T)$, both the components of $T-e$ have odd order. Prove that all the vertices of $T$ have odd degree.
7
votes
2answers
363 views

If a graph has a Hamilton Path starting at every vertex, must it contain a Hamilton Circuit?

If a graph $G$ has at least three vertices, and has a Hamilton Path starting at every vertex, must it contain a Hamilton Circuit? I have been struggling with this problem. It seems that because ...
1
vote
0answers
20 views

Determine the multiplicity of knots for a graph

Here are my two questions: Given a finite connected non-oriented planar graph, is there a way to determine whether or not it is possible to derive a single non-trivial knot diagram from this graph, ...
0
votes
1answer
36 views

What is this total length

What is the value of the total length of all the edges connecting the vertices of a regular $k$-gon that is inscribed on a unit circle?
1
vote
2answers
60 views

Graphs with pairs of vertices connected by multiple edges

Is there a common name for this kind of graphs (directed or not)? Thank you.
0
votes
0answers
405 views

What is the equation for the average path length in a random graph?

If we have random network/graph having a number of vertices $N_v$ and there number of edges $N_e$, how do we calculate the average path length between two random ...
0
votes
0answers
462 views

A graph with 20 edges has 5 vertices of degree 5 with the rest of degree 4. How many vertices of each degree does it have?

Actually, I have an answer and it is pretty simple to be obtained. You just have to use the classical theorem that states that the sum of all degrees of the graph is equal twice the number of edges. ...
0
votes
1answer
96 views

Problems in tree

Please give me some hints for the following problems. Many thanks in advance, Prove that For any three nodes $ u $ , $ v $ and $ w$ of a tree $ d(u,v)+d(v,w)+d(u,w)\equiv 0$ (mod 2). For any four ...
0
votes
1answer
67 views

unranking a sequence of all linear extensions of a partially ordered set

Let $P$ be a partially ordered set. Let $E$ be the set of all possible linear extensions of $P$. Let $S$ be the sequence formed by arranging elements of $E$ in lexicographic or graycode order. Does ...
1
vote
2answers
51 views

How is this statment not contradictory?

Let $$C = v_0, v_1,...,v_k, v_0$$ be a longest circuit in G. Suppose C is not a Eulerian circuit. By longest circuit don't they mean every vertex is visited? How is this different than a Eularian ...
0
votes
1answer
90 views

graph orientation with constraint on incoming degree

Consider the following graph orientation problem: we would like to orient the edges of a graph G in such a way that each vertex has at most k incoming edges. Prove that this is possible if and only if ...
3
votes
0answers
58 views

Is the upper Cheeger Inequality tight?

The (upper) Cheeger Inequality says: Let $G$ be an unweighted, undirected, regular graph of degree $d$. Let $\lambda_2$ be the second eigenvalue of the Laplacian matrix of $G$, and let $\phi(G)$ ...
0
votes
1answer
1k views

When does a closed walk not have a cycle?

Closed walk: sequence of vertices and edges where the first vertex is also the last Cycle: closed walk where all vertices are different (except for first/last) I can't think of an example where a ...
0
votes
1answer
95 views

What does it mean for a closed walk and cycle to be of “odd length”?

What does it mean for a closed walk to be odd length? Is it counting the number of edges or vertices? Same for cycle.
1
vote
1answer
63 views

Does the way a graph $G$ is encoded affect the proof that $CLIQUE$ is in $NP$?

For a proof that $CLIQUE = \{ \langle G, k \rangle | G$ is an undirected graph with a $k$-clique. $\}$ is in $NP$ by constructing a nondeterministic Turing machine $N$, where $N$ = $``$On input ...
0
votes
1answer
51 views

Proving that a graph that is connected but not complete has vertices u,v and w such that uv and vw are edges but not uw

The task is prove that a graph G(V, E) that is connected but not complete there are vertices u, v and w such that uv,vw are in E but vw is not in E. First off I'm not sure this is true. u and w could ...
0
votes
1answer
27 views

Question Concerning Family of Trees

I have the following problem where I am asked to construct a family of trees (one for each $n$) that have exactly 2 leaves. I am having difficulty with this problem mainly because I cannot find a ...
1
vote
0answers
122 views

Node mapping with edge weights

For an academic paper, I wish to use node mapping and weighted edge. I do not understand the concepts quiet clearly. I have a weight on each edge. The graph for which am trying to solve the problem ...
1
vote
2answers
646 views

Prove Four Statements Are Equivalent

I have the following problem, where $G$ is a graph with $n$ vertices, prove the following statements are equivalent: 1. $G$ is connected and acyclic 2. $G$ is connected and has $n-1$ edges 3. $G$ ...
1
vote
0answers
74 views

“Das ist das Haus vom Nikolaus” and Euler cycle

Consider the following graph $(V,E)$: With $a, b, c, d, e \in V$. Then I obviously can make an Euler cycle: $[b, a, c, e, d , c, b, e, a]$. But it also holds that $deg(a)=deg(b)=3$ which is not ...
2
votes
0answers
57 views

Does the notion of graph with vertex multiplicity exist?

I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have. It is actually a way to write in a ...
1
vote
1answer
188 views

Difference between isomer and isomorph

In graph theory what is the difference between isomerism and isomorphism? I found a post somewhat similar to it but couldn't understand my problem from that. So I asked again specifically asking my ...
0
votes
1answer
89 views

edge disjoin Cut Set

prove that a graph G=(V,E) where | v | =n there are at most n-1 edge disjoint cut sets. I was thinking that for tree it is true since each edge is cut set. but i have no idea how to prove above ...
1
vote
2answers
425 views

Prove that Hamming cube has a Hamiltonian cycle

How would one prove that all Hamming cubes with 2 or greater dimensions have a Hamiltonian cycle.
1
vote
0answers
48 views

automorphism of a rooted tree

Nowadays i'm working with tree automorphisms. I couldn't find information about rooted tree automorphism concerning the root. Does an automorphism of a rooted tree fix the root or not? Logically it ...
1
vote
1answer
175 views

Shortest path calculation

I have a given set of start points, a given set of end points. Each start point corresponds to one endpoint. I have to visit all start points, and then the corresponding end points, in the most ...
2
votes
0answers
123 views

a question about odd cycle

I have a conjecture about odd cycle in a simple graph,but I can not proof it or find a counterexample.So I want to ask for some help.My conjecture is: Let k be a positive integer and G be a ...
0
votes
1answer
62 views

meaning of $C_4$ tree in graph theory

I was reading a paper. There a term was defined as $C_4$ tree. It was written that a graph is $C_n$ tree if it can b constructed from $C_n$ by a finite number of applications of the following theorem ...
0
votes
3answers
105 views

Bipartite Graphs

I know that graph G is bipartite iff G does not contain any odd cycle. Does it mean that G is not bipartite iff G contains any odd cycle ? Thanks in advance
1
vote
1answer
114 views

What's this graph? (8 vertices, 16 edges)

Let $G = (V,E) =$ f------g |`. |`. | `a--+---b | | | | e---+--h | `. | `. | . `d------c Now let $G' = (V,\, E \cup \{\{a,h\}, \{b,e\}, \{c,f\}, ...
1
vote
0answers
135 views

prove matroid conditions

can anybody please help me to prove bicircular matroid is a matroid, from the direct definition of bicircular graph, it is also called pseudoforest. So we define the independent set to be the edge ...
2
votes
2answers
1k views

Prove that in a simple graph there is a path from any odd vertex to any odd vertex?

Let $k$ be the number of vertices. If $k = 1$, then the point is isolated and therefore has degree 0; WLOG, we can assume that no point is isolated. With $k = 2$, there is a vertex of ...
0
votes
1answer
173 views

How do I prove that a graph if Hamiltonian it must be 2-connected?

I understand that a graph is biconnected if each vertex has degree > or equal to 2. Is it enough to say that a Hamiltonian Graph contains a cycle and every cycle has a least the degree of 2?
2
votes
1answer
459 views

Graph Theory: Nontrivial tree has independent sets.

Prove that every nontrivial tree has at least two maximal independent sets, with equality only for stars. Since a tree has no cycles, it has no odd cycles. Hence it is bipartite so, by definition, it ...