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

1
vote
1answer
376 views

Do alternating and augmented paths for a matching need to cover all the edges in the matching?

Definition for alternating paths and augmented paths of a matching in a graph is defined as follows: Given a matching M, an alternating path is a path in which the edges belong alternatively to ...
0
votes
1answer
164 views

Prove that there exists a set $\{C_1,\ldots,C_m\}$ of cycles in $G$.

Hello, I'm new to combinatorics so I'm having a bit of trouble. The question I'm having trouble with goes like this: Let $W=v_0e_1v_1\ldots e_nv_n$ be a walk in a graph $G$, such that $v_0 =v_n$ ...
1
vote
2answers
779 views

How does the Kronecker delta work for matrices?

I am trying to understand the effect of the kronecker delta function in this expression $\sum_{i,j}(1+\delta_{i,j})M_{ij}$ given that $M$ is a matrix with real-entries. How does this operation work!? ...
0
votes
1answer
93 views

If $G$ has an induced $K_n$, show the chromatic number $\chi(G)\ge n$.

How to show that if G has an induced subgraph which is a complete graph on n vertices, then the chromatic number is at least $\chi(G)\ge n$.
3
votes
1answer
59 views

Does the parameters $d, a, b$ uniquely determine a strongly regular graph?

The existence is not guanranteed of a strongly regular graph, $d$-regular, every pair of adjacent vertices having $a$ common neighbors, every pair of vertices not adjacent having $b$ common neighbors. ...
2
votes
2answers
577 views

Coloring Graph Problem

If G is a graph containing no loops or multiple edges, then the edge-chromatic number $X_e(C)$ of G is defined to be the least number of colours needed to colour the edges of G in such a way that no ...
3
votes
1answer
159 views

Cubic (3-regular) graph spanning tree

Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes): Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 ...
1
vote
1answer
251 views

Is every planar graph without triangles 3-colorable?

In other words, can a planar graph without k3 have a chromatic number larger than 3?
2
votes
1answer
475 views

Sub-Graph of a Minimum Spanning tree

I am going through all the exercises in my book for revision of a class test next week, and i am really confused about this sub-graph question. Currently my thinking leads me to believe that since ...
1
vote
0answers
29 views

Terminology: a notion of a set of “chords” for arbitrary subgraphs

I'm considering a problem on random graphs, where it makes sense to look the edges which "touch" a connected component, but which do not belong to it. Consider a fixed graph $G$, where as usual we ...
1
vote
1answer
2k views

Relations between the maximum matching, minimum vertex cover, maximum independent set, and maximum vertex biclique for a bipartite graph

From Wikipedia: König's theorem states that, in bipartite graphs, the maximum matching is equal in size to the minimum vertex cover. Via this result, the minimum vertex cover, maximum ...
3
votes
4answers
778 views

Can a graph be non 3-colourable without having k4 as a sub graph?

As the question asks, is it possible for a graph to have a chromatic number larger than three without it having a 4 vertice complete graph as a sub-graph?
0
votes
2answers
705 views

Prove that the minimum number of cycles is $m-n+1$

The question I have is: Prove that the minimum number of cycles is $m-n+1$ in a connected graph. Where one cycle is a path that starts that begins and ends at the same vertex. Where $m$ is edges and ...
0
votes
0answers
139 views

Strong tournaments, degree sequences, isomorphism

This is a follow-up to an earlier question. Suppose you start at a given score sequence, and ask "how many tournaments, up to isomorphism, have this score sequence?" For {0, 1, 2, ..., n-1} the ...
1
vote
0answers
175 views

Score Sequences Of Tournaments And Isomorphism

There are a lot of papers on degree/score sequences of tournaments, starting on a given sequence, and constructing a tournament that has that degree sequence, and so forth. But what if you start at ...
3
votes
1answer
1k views

Definition of clique cover and clique edge cover

From Wikipedia The clique cover problem (also sometimes called partition into cliques) is the problem of determining whether the vertices of a graph can be partitioned into k cliques. It ...
4
votes
2answers
158 views

Structure of $x^2 + xy + y^2 = z^2$ integer quadratic form

The pythagorean triples $x^2 + y^2 = z^2$ can be solved in integers using rational parameterization of solutions to $x^2 + y^2 = 1$. It goes through $(1,0)$, then consider the line $y = -k (x - 1)$ ...
4
votes
0answers
174 views

Tilings of the plane

There are many possible tilings (or tesselations) of the plane: periodic ones by a - necessarily - finite number of prototiles (e.g. regular tilings) aperiodic ones by a finite number of prototiles ...
2
votes
0answers
47 views

Terminology: is there a term for one order being on a geodesic between two others in the Cayley graph?

Think about the graph whose nodes are total orders on a finite set, and whose edges connect orders that only differ on two elements. This is actually a Cayley graph of $S_n$, but I don't want to fix ...
0
votes
1answer
75 views

planar Graph problem

In a planar representation of G , every regions (for example $R_1$) surrounded with even EDGES. Prove that : G is bipartite. (I think can use "G has no odd cycles then G is bipartite.")
0
votes
2answers
257 views

Deficient Tutte's Theorem

Everyone knows the Tutte's Theorem (necessary & sufficient condition for a graph to have a perfect matching - viz wikipedia page on Tutte's Theorem). The deficient version of this Theorem is: ...
0
votes
1answer
270 views

Kruskal's algorithm proof

I'm having trouble understanding part of the proof of Kruskal's algorithm. In the notes that our professor gave us, he has this: Ok so this is missing some things. Unfortunately the lecture does ...
2
votes
0answers
70 views

Do line graph and dual graphs induce symmetric relations on graphs?

Let $L(G)$ be the line graph of a graph $G$. Is $G$ the line graph of $L(G)$? From the same article: Properties of a graph $G$ that depend only on adjacency between edges may be translated ...
1
vote
1answer
160 views

Is skew symmetry required for a flow network?

From Wikipedia: $G(V,E)$ is a finite directed graph in which every edge $\ (u,v) \in E$ has a non-negative, real-valued capacity $\ c(u,v)$. A flow network is a real function $\ f:V \times V ...
0
votes
1answer
961 views

Relation between sizes of matching, edge cover, independent set and vertex cover

From Wikipedia: A perfect matching is also a minimum-size edge cover. Thus, the size of a maximum matching is no larger than the size of a minimum edge cover. I know that a perfect matching ...
1
vote
1answer
2k views

Graph Theory Shortest Path Problem via Matrix Operations in MatLab

Here is something that has been getting the best of me for past few days. Hopefully someone can point me get in the right direction. I have a graph G, and I need ...
0
votes
1answer
71 views

N-Regular graph problem

Suppose that G be a bipartite graph with maximum degree of k. Prove that: 1)Exists a K-regular bipartite graph that G be subgraph it(H)
0
votes
1answer
357 views

What is the definition of a network in graph theory

From Wikipedia a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot ...
1
vote
1answer
444 views

Defining a cut-set without referring to partitioning vertices into two groups?

From Wikipedia: a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the ...
0
votes
1answer
79 views

Arc transitivity of the complete graph

Recall that a graph $G$ is arc transitive if the natural action of $\mathrm{Aut}(G)$ on $A(G) = \{ (u,v) | \{u,v\} \in E(G)\}$ is transitive. In other words, given $(u,v),(u'.v') \in A(G)$ one finds ...
7
votes
3answers
1k views

Eigenvalues of a bipartite graph

Let $X$ be a connected graph with maximum eigenvalue $k$. Assume that $-k$ is also an eigenvalue. I wish to prove that $X$ is bipartite. Now if $\vec{x}=(x_1,\cdots ,x_n)$ is the eigenvector for ...
0
votes
1answer
133 views

Network Simplex Method: How to relabel the vertices and arcs such that the truncated matrix is upper triangular and non-singular.

Suppose $G = (V, A)$ is the acyclic weakly connected digraph with$ V $consisting of vertices $v_{i}$ $(i = 1, 2, ..., 8)$ in which the seven arcs are $(v 1 , v 2 ), (v 3 , v 2 ), (v 4 , v 3 ),(v 7 , v ...
1
vote
1answer
37 views

Alternative interpretation of graph-minor theorem

I have read some paper claim about graph-minor theorem that "Another equivalent form of the theorem is that, in any infinite set S of graphs, there must be a pair of graphs one of which is a minor of ...
1
vote
2answers
3k views

Hamilton,Euler circuit,path

For which values of m and n does the complete bipartite graph $K_{m,n}$ have 1)Euler circuit 2)Euler path 3)Hamilton circuit I found answers and you Prove(or show)that: 1)($K_{m,n}$ has a Hamilton ...
2
votes
1answer
303 views

Connectedness of a regular graph and the multiplicity of its eigenvalue

Suppose $X$ is a $k$-regular graph with adjacency matrix $A$. I wish to show that if $k$ has multiplicity $1$ as an eigenvalue of $A$ then $X$ is connected. By way of contradiction I assume that X is ...
0
votes
1answer
577 views

Every edge with even degree -> Euler tour

Euler tour is a closed walk that can traverse each edge in a graph exactly once. If every edge in a connected undirected graph has even degree, how can you prove that it has an Euler tour?
1
vote
1answer
162 views

Usage of Cauchy-Schwarz on graphs

Preface. I am reading up on the Chung-Graham-Wilson results on quasi-random graphs, and the description I'm reading is applying an apparently obvious usage of Cauchy-Schwarz that I'm just not seeing. ...
3
votes
1answer
792 views

The number of non-isomorphic spanning trees in K4

K4 has 16 spanning trees. I believe there are two non-isomorphic spanning trees in K4. Is this because half of the spanning trees have the sequence (1,2,2,1) as the degrees of their vertices, while ...
1
vote
2answers
79 views

For which $n$ is the graph $C^2_n$ planar?

Let $C_n$ be the simple cycle with $n$ vertices. Let $C^2_n$ be the graph obtained from $C_n$, and includes all the edges $C_n$ plus the edges $\{(u,v) : \mathrm{dist}(u,v) = 2\}$ in $C_n$. For which ...
1
vote
1answer
36 views

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set. Give some clue please! Thanks anyway!
2
votes
1answer
63 views

Decide probabilistically whether leaf labels in a decision tree sum to zero?

I have the following problem, which might or might not be very easy to answer for someone with even a light background in statistics - but I don't even know where to start. Hence, I will give it a ...
2
votes
1answer
119 views

Count possible traversals in an undirected graph

A graph of $n$ nodes is given. We have to visit each node twice. How many such traversals are there? It's a complete graph and it's not possible to visit the nodes in a consecutive order. Example: ...
0
votes
1answer
76 views

build a graph with smallest diameter, N verteces, each vertex has degree $\ge k$

I need to build a graph with number of vertexes N such that each vertex has degree at least k and the graph has the smallest diameter. I believe that this question should be well studied. EDIT: yes ...
1
vote
0answers
251 views

Finding all spanning trees of a strongly connected directed graph

I have a strongly connected directed graph with about 10 vertices and 20 edges, and would like to find all spanning trees anchored at each vertex. Is there a systematic way, or a tested ...
0
votes
1answer
175 views

Topological sort of a subgraph

If I have a graph $G$ and a subset $G'$, for all topological sorts $S$ over $G$, is there a topological sort over $G'$ that is a subset of $S$? As a software optimization I want to pre-compute $S$ ...
2
votes
2answers
236 views

Proof a bipartite graph problem

Prove that: a simple graph is a bipartite graph if and only if lenght of all circuits in graph be even. (give me answer or hint or idea)
2
votes
0answers
116 views

Almost regular graphs that are Hamiltonian

It is known that every $r$-regular graph on $2r+1$ vertices is Hamiltonian (Nash-Williams theorem, see here). Now, I wonder if there is a simpler way to show that the graph on $4n+3$ ($n \ge 1$) ...
2
votes
1answer
118 views

Is it possible to make a graph eulerian by adding exactly one node?

Let $G=(V,E)$ denote a connected graph with $|V|\geq 2$. Is it possible to add a new node $v$ with corresponding edges $e_k=\{v,w\}$ with $w\in V$(*1) such that $(V\cup\{v\},E^\prime)$ contains an ...
6
votes
3answers
568 views

Number of maximum components of a graph once any one vertex is removed

Let $G$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $G$, the number of components in the resultant graph must necessarily lie between$\ldots$? I figured ...
1
vote
0answers
56 views

Can you consider a directed graph the discretization of a 2-manifold equipped with a vector field?

Can you consider a directed graph the discretization of a 2-manifold equipped with a vector field? Thanks