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

10
votes
4answers
955 views

How many “good” graphs of size $n$ are there?

Let's a call a directed simple graph $G$ on $n$ labelled vertices good if every vertex has outdegree 1 and, when considered as if it were undirected, it is connected. How many good graphs of size $n$ ...
0
votes
1answer
47 views

Minimal cuts in network.

Let $(S_1, \overline{S_1} ) , (S_2, \overline{S_2} )$ be minimum cuts in some network. Thesis: The $(S_1 \cap S_2, \overline{S_1 \cap S_2)}$ is minimum cuts in this network. Thesis is true? Why? I ...
0
votes
1answer
45 views

Is it possible to apply properties of nodes in a graph to its edges?

I have a graph whose vertices represent points in geometric space. The edges of this graph represent line segments between various points. Is it possible to assign a direction to an edge based on ...
3
votes
1answer
66 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...
3
votes
1answer
77 views

How many subgraphs of $K_{m,n}$ are there that contain m + n vertices?

In this problem, a subgraph of $G = (V,E)$ is given by $G' = (V', E')$ where $V' \subset V$ and $E'$ is subset of edges of $E$ that connect two vertices in $V'$. How many subgraphs of $K_{m,n}$ are ...
1
vote
1answer
140 views

Counting the number of unicyclic graphs

Could you help me giving me the number of unicyclic graphs with k vertices and k edges ? I remind that a unicyclic graph with k vertices and k edges is a tree with k vertices and k-1 edges to wich we ...
1
vote
1answer
840 views

Directed Multigraph or Directed Simple Graph?

I have the following two questions in my book: Question # 1 Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops....
0
votes
1answer
51 views

Finding representation matrix of $M$*$(K_5)$ above $\mathbb F_2$

Finding representation matrix of $M$*$(K_5)$ above $\mathbb F_2$. $M$*$(K_5)$ is the dual matroid representing the graph $K_5$, that is, a complete graph with 5 vertices. How do I solve this? We'...
5
votes
1answer
73 views

Special case of Minimum Spanning Tree

I have been bashing my head trying to solve the following problem for the past two days, it is a review question in preparation for my exam and I assume something similar will be on it. The problem ...
0
votes
1answer
39 views

Extension of hypercube

I understand the notion of a hypercube as a graph with vertex set $\{0,1\}^{n}$ and an edge between two vertices if their vertices differ in one co-ordinate is there an extensive body of work on the ...
0
votes
1answer
143 views

How can a bipartite simple graph be non isomorphic

From my understanding the bipartite graph is a graph that follows the red blue color scheme. If the graph fails the red blue color, then the graph is not bipartite. But the question how do you test a ...
1
vote
1answer
61 views

Removal of cut edge disconnects this graph

I am not sure how does removing cut edge {a,b} disconnects the graph. My interpretation of disconnect means when the graph has multiple components. Original graph before removal graph after ...
3
votes
1answer
203 views

A consequence of the fan lemma for graphs (a theorem of H. Perfect)

Let $G$ Be a graph, $x$ a vertex of $G$ and $Y$ and $Z$ subsets of $V - \{x\}$ and $|Y| < |Z|$. Suppose there are fans from $x$ to $Y$ and from $x$ to $Z$. I want to show that there exist $z \in Z-...
3
votes
2answers
245 views

why is the Petersen Graph the smallest hypohamiltonian graph?

I know that the Petersen graph is hypohamiltonian. (Which means it is not hamiltonian, but each vertex-deleted subgraph is.) Why is it the smallest hypohamiltonian graph? (without considering $K_2$ )...
3
votes
0answers
72 views

Complete bipartite graphs with odd/even edge conditions

Given a simple graph $G$ with $n$ vertices. Prove that there exist simple graphs $S_1,\ldots,S_k$ with $k\leq\frac34n$, such that every $S_i$ is a complete bipartite graph, every edge of $G$ is ...
1
vote
1answer
131 views

show that a loopless graph $G$ contains a bipartite spanning subgraph $H$ such that $d_H(v) \ge \frac{1}{2} d_G(v)$ for all v $\in$ V.

The hint in the appendix of book says that bipartite subgraph with with largest possible number of edges has such a property, but I don't know how to use this hint! any help would be appreciated.
1
vote
2answers
143 views

graph theory “ three nodes of degree 0 1 3 respectively”

Does this graph exist " 3 nodes of degree 0 1 3 respectively" i don't think so because if you have a degree of zero it would be disconnected from the other 2 nodes and on that premise you cannot ...
0
votes
0answers
411 views

Number of ways to connect N nodes with K edges.

Given a graph with N nodes, I have to find the number of different ways the nodes can be connected with the K edges such as the resulting graph is connected. For N = 3 and K = 2, the possibilities ...
2
votes
1answer
47 views

Showing non existence of topological minors in a graph

Recall that a subgraph $H$ of $G$ is called a topological minor if by only adding vertices, edges to $H$ and subdividing some edges of $H$ one can construct $G$. For small graphs, it is easy to show ...
0
votes
3answers
154 views

Proof n-cube graph is connected

I am studying graph theory and my text book gives a proof for an n-cube graph being connected that I find really weird/confusing. Is there a simpler proof to show that the n-cube is connected. The n-...
1
vote
0answers
20 views

concerning Graph Theory/subgraphs/ even degree [duplicate]

Given a simple Graph $G=(V,E)$ ($V$ vertices, $E$ edges) I have to show that there exists a distribution $V= V_1 \cup V_2$ of the vertices such that all vertices in the induced subgraphs $G[V_1]$ and $...
1
vote
1answer
212 views

Given n vertices, how many unique graphs can be drawn with k edges?

I am not a mathematician. I've been working on a problem for some time, and I can't seem to be able to grasp the solution. I need to find an algorithmic way to solve for the number of connected, ...
3
votes
2answers
158 views

Given a simple connected bipartite graph $G$ with degree of vertices equal to $k$, where $k\ge 2$. Prove that there is no cut vertex exist in $G$.

Given a simple connected bipartite graph $G$ with degree of vertices equal to $k$, where $k\ge 2$. Prove that there is no cut vertex exist in $G$. Cut vertex $v$ here is a vertex which make the ...
1
vote
1answer
63 views

calculating a chromatic polynomial

I am going through some questions in the "Bondy,Murty - Graph Theory with applications" book, and I have stumbled upon the following question: calculate the Chromatic Polynomial of the following ...
1
vote
0answers
102 views

Induced cycle of odd length in a large graph

I'm trying to prove the following result in order to solve a different problem but I'm stuck; however I'm not sure if it is true, so I'll pose it as a question; Suppose we have a triangle-free ...
1
vote
1answer
147 views

Spectrum of infinite d-regular tree

Consider the adjacency matrix of the infinite d-regular tree, call it A. To find the spectrum we consider it as an operator in $L^2(V)$. It is stated that $A-\lambda I$ is always one-to-one. I do ...
1
vote
2answers
566 views

Number of connected components in a graph with n vertices and n-k edges

Suppose that we have a graph G with n vertices and n-k edges, such that it does not include any cycles. How many components does it have? I am coming up with k components but am having a hard time ...
0
votes
1answer
29 views

Triangular inequality in weighted graphs

In a finite directed complete graph $G ( V, E )$, if all edges have weight either $1$ or $2$, how to show that weights of edges of $G$ satisfies "Triangular Inequality"? Edited Where triangular ...
0
votes
1answer
43 views

Brook's theorem. Where I make a mistake?

please explain me one thing: According to Brook's theorem $ \chi(G ) \le \deg(u) $ But it can't be true. After all, there are $\deg(u) + 1 $ colors and I'm enclosing a draw. http://i.imgur.com/...
0
votes
1answer
64 views

How many trees can be drawn using$n$ vertices without rebuilding isomorphs?

I'm told to draw all possible trees with exactly $6$ vertices. I was able to draw a maximum of $6$ trees. Any more were isomorphs of these $6$ trees. How can I determine if I have drawn all the trees? ...
5
votes
1answer
367 views

A partition of vertices of a graph

I've got an example for this question, but there are many different possibilites and I don't know how to show this for all graphs. Has got anyone any advice how to begin ? Let $G=(V,E)$ be an ...
0
votes
2answers
52 views

Can anyone give an example for this theorem related to planar graphs?

Theorem: Let $G$ be a connected planar graph with $p$ vertices and $q$ edges, where $p\geq 3$. Then $q\leq3p-6$. Proof: Let $r$ be the number of regions in a planar representation of $G$. By ...
5
votes
2answers
162 views

Vertex-transitive graphs and deletion of vertices

Consider the following graph property: for each $u, v \in V(G)$, we have that $G - u \cong G-v$. This property implies a high "symmetry" of the graph. We can easily see that every vertex-transitive ...
2
votes
1answer
40 views

Number of spanning trees in $K_9$ with the degree of vertex $1$ being $4$

I believe I've gotten this problem, but I'm not sure whether I'm correct, because my familiarity with Prufer codes is very weak. I would appreciate any corrections / comments on the mistakes I've made....
1
vote
0answers
736 views

Proof of Hamilton Cycle in a Complete Bipartite Graph

For a complete Bipartite graph K(m,n) has a Hamilton cycle if and only if m=n. I want to know if the following proof technique is correct. My proof will consider using proof by contradiction. Assume ...
0
votes
1answer
42 views

Proof that there exists complete matching.

Given is bipartite graph $G = (V_1 \cup V_2, E)$. Prove that if $\exists m \in \mathbb{N} : \forall x \in V_1 , \forall y \in V_2 $ $\delta(x) \ge m \ge \delta(y) $ then exists complete matching. ...
1
vote
1answer
228 views

Proving every planar graph have vertex cover of size of at most 3n/4

Question title says it all: How it can be proved that every planar graph on n vertices have vertex cover of size of at most 3n/4. I came across this fact when I was reading a textbook. However I am ...
1
vote
0answers
25 views

Proof with chromatic index. [duplicate]

Prove that for $G = (V,E) $ $$ \chi(G) \chi(\overline{G}) \ge |V| $$ Please for some advices. Thanks in advance.
7
votes
1answer
119 views

Can a planar graph be drawn with all vertices on a straight line?

I have been repeatedly trying to prove and disprove the following: Can any planar graph, with $n$ vertices, be drawn such that the vertices are fixed at coordinates $(0,0)$, $(1,0)$, ..., $(n-1,0)$...
3
votes
1answer
59 views

Tool for construction of graph with specified properties

Is there a tool (class of algorithms for graph generation) that can construct graph with specified properties. E.g. construct graph who is homeomorphic with both to K5 and K3,3. Construct planar graph ...
3
votes
1answer
38 views

Can deleting an edge from a graph create a single subgraph?

This is a question on Graph Theory. The book says : 1) If $v$ is a vertex in $G$, then $G-v$ is the subgraph of $G$ obtained by deleting $v$ from $G$and deleting all edges in $G$ which contain $v$...
2
votes
1answer
75 views

Determine the number of loops

Determine the number of loops for a given multigraph $G$ ($|V| \geq1$) from Tutte's polynomial $T_G(x,y)$. Okay, so I tried calculating the total number of edges, which I can get from $T_G(2,2)$, ...
0
votes
1answer
44 views

Longest Path in a acyclic, directed graph

Is there a known algorithm which finds the longest path in an acyclic, directed graph like the one below? For this example, the algorithm should calculcate a longest path of 28m
0
votes
1answer
59 views

Relation between independence number and channel capacity

Suppose $P_{Y|X}$ is a discrete memoryless channel with confusability graph $G$ and capacity $C = max_{P_X}I(X; Y )$. I want to prove the following relation: $\log{\alpha(G)}\le C$ where $\alpha(G)$ ...
0
votes
3answers
406 views

Perfect matching in k-cubes

I want to show that every k-cube has a perfect matching for $ k \geqslant 1 $. (A k-cube is a graph whose vertices are labeled by k-tuples consisting of $ 0 $ and $1$ , and each two adjacent vertices ...
0
votes
2answers
125 views

In how many ways you can represent a graph ( data type )?

I need some references that go beyond the classical and graphical representation of a graph with vertices and edges; I'm trying to dive into the math world and see if I can get an alternative ...
1
vote
1answer
72 views

Simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph

Why a simple connected bipartile graph $G=(V,E)$ with $10$ vertices of degree 3 cannot be a planar graph? In my notes, it says it is easy and leave as an exercise with a hint which want us to show the ...
0
votes
1answer
44 views

Expectation of number of links to N selected nodes in a network

Take a directed graph denoted by its adjacency matrix $\mathbf{A}$. It is a probabilistic graph -- the nodes of $\mathbf{A}$ might be linked, and the entries are probabilities between 0 and 1. Say ...
0
votes
2answers
535 views

Proof NP-Complete for $L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$

$L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$ and I try to prove it's NP-Completeness. It seems really easy since obviously it is at least as hard as HAM-PATH which is ...
2
votes
1answer
43 views

Why doesn't Tutte polynomial T(1,1) equal 0?

If the formula for a Tutte polynomial is: then how does T(1,1) solve for spanning trees instead of just returning a 0?